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; }