AOJ 1315 Gift from the Goddess of Programming

区間[a,b]と[c,d]の共通部分の長さはmax(0,min(b,d)-max(a,c))であることに注意して全探索する。最初、配列を小さく取り過ぎてREした。

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
typedef pair<int,int> P;

int blessedTime(int a0,int b0,int a1,int b1){
    int aa=max(a0,a1);
    int bb=min(b0,b1);
    return max(0,bb-aa);
}

int main(){
    int n;
    while(cin >> n && n){
        vector<vector<P> > pr(600);
        REP(i,n){
            int M,D,h,m,p;
            string e;
            scanf("%d/%d %d:%d",&M,&D,&h,&m);
            cin >> e;
            scanf("%d",&p);
            int time=m+h*60+D*24*60+M*31*24*60;
            if(e=="I"){
                pr[p].push_back(make_pair(time,-1));
            }else{
                pr[p][pr[p].size()-1].second=time;
            }
        }
        int bt[600]={};
        for(int i=1;i<600;i++){
            REP(j,pr[i].size()){
                REP(k,pr[0].size()){
                    bt[i]+=blessedTime(pr[0][k].first,pr[0][k].second,pr[i][j].first,pr[i][j].second);
                }
            }
        }
        sort(bt,bt+600);
        cout << bt[599] << endl;
    }
    return 0;
}