Submission #520877


Source Code Expand

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;

const int DEBUG = 0;

struct mov {
	int m, s, e;
};

istream &operator>>(istream &os, mov &m) {
	os >> m.m >> m.s >> m.e;
	return os;
}

bool mov_cmp(const mov &m1, const mov &m2) {
	return m1.s < m2.s;
}

int solve(vector<int> &h, vector<mov> &ms) {
	int n = h.size();
	vector<map<int, int> > dp(n);
	vector<int> dpm(n, -1);
	REP(i, 0, n) {
		dp[i] = map<int, int>();
	}
	REP(i, 0, n) {
		dp[i][1] = h[0];
		REP(k, 0, i) {
			if (ms[k].e > ms[i].s) {
				continue;
			}
			if (ms[k].m != ms[i].m && dpm[k] >= 0) {
				dp[i][1] = max(dp[i][1], dpm[k] + h[0]);
			} else {
				for (map<int, int>::iterator it = dp[k].begin();
						 it != dp[k].end(); ++it) {
					dp[i][it->first + 1] = max(dp[i][it->first + 1], it->second + h[it->first]);
				}
			}
		}
		for (map<int, int>::iterator it = dp[i].begin();
				 it != dp[i].end(); ++it) {
			dpm[i] = max(dpm[i], it->second);
		}
	}
	int ma = 0;
	REP(i, 0, n) {
		ma = max(ma, dpm[i]);
	}
	return ma;
}

int main(void) {
	int n;
	cin >> n;
	vector<int> h(n);
	vector<mov> ms(n);
	REP(i, 0, n) {
		cin >> h[i];
	}
	REP(i, 0, n) {
		cin >> ms[i];
	}
	sort(ms.begin(), ms.end(), mov_cmp);
	cout << solve(h, ms) << endl;
}

Submission Info

Submission Time
Task D - 映画の連続視聴
User kobae964
Language C++ (G++ 4.6.4)
Score 0
Code Size 1532 Byte
Status TLE
Exec Time 2042 ms
Memory 13072 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 41
TLE × 20
Set Name Test Cases
All subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask1_34.txt, subtask1_35.txt, subtask1_36.txt, subtask1_37.txt, subtask1_38.txt, subtask1_39.txt, subtask1_40.txt, subtask1_41.txt, subtask1_42.txt, subtask1_43.txt, subtask1_44.txt, subtask1_45.txt, subtask1_46.txt, subtask1_47.txt, subtask1_48.txt, subtask1_49.txt, subtask1_50.txt, subtask1_51.txt, subtask1_52.txt, subtask1_53.txt, subtask1_54.txt, subtask1_55.txt, subtask1_56.txt, subtask1_57.txt, subtask1_58.txt, subtask1_59.txt, sample_01.txt, sample_02.txt
Case Name Status Exec Time Memory
sample_01.txt AC 37 ms 1152 KB
sample_02.txt AC 31 ms 1048 KB
subtask1_01.txt AC 154 ms 4492 KB
subtask1_02.txt AC 31 ms 1168 KB
subtask1_03.txt AC 111 ms 3596 KB
subtask1_04.txt AC 257 ms 6432 KB
subtask1_05.txt AC 61 ms 2320 KB
subtask1_06.txt AC 233 ms 5892 KB
subtask1_07.txt AC 34 ms 1292 KB
subtask1_08.txt AC 95 ms 3212 KB
subtask1_09.txt AC 35 ms 1396 KB
subtask1_10.txt AC 213 ms 5876 KB
subtask1_11.txt AC 35 ms 1424 KB
subtask1_12.txt AC 97 ms 3336 KB
subtask1_13.txt AC 155 ms 4624 KB
subtask1_14.txt AC 260 ms 6540 KB
subtask1_15.txt AC 329 ms 7816 KB
subtask1_16.txt AC 327 ms 7812 KB
subtask1_17.txt AC 340 ms 7692 KB
subtask1_18.txt AC 326 ms 7672 KB
subtask1_19.txt AC 316 ms 7696 KB
subtask1_20.txt TLE 2041 ms 13068 KB
subtask1_21.txt TLE 2041 ms 13072 KB
subtask1_22.txt TLE 2038 ms 12940 KB
subtask1_23.txt TLE 2040 ms 12928 KB
subtask1_24.txt TLE 2038 ms 12944 KB
subtask1_25.txt TLE 2039 ms 12944 KB
subtask1_26.txt TLE 2041 ms 13068 KB
subtask1_27.txt TLE 2040 ms 13068 KB
subtask1_28.txt TLE 2038 ms 13068 KB
subtask1_29.txt TLE 2038 ms 13072 KB
subtask1_30.txt TLE 2041 ms 13068 KB
subtask1_31.txt TLE 2041 ms 12960 KB
subtask1_32.txt TLE 2040 ms 12932 KB
subtask1_33.txt TLE 2041 ms 13060 KB
subtask1_34.txt TLE 2039 ms 13064 KB
subtask1_35.txt TLE 2042 ms 13044 KB
subtask1_36.txt TLE 2038 ms 12940 KB
subtask1_37.txt TLE 2040 ms 13072 KB
subtask1_38.txt TLE 2040 ms 12948 KB
subtask1_39.txt TLE 2040 ms 13072 KB
subtask1_40.txt AC 322 ms 7692 KB
subtask1_41.txt AC 326 ms 7820 KB
subtask1_42.txt AC 328 ms 7692 KB
subtask1_43.txt AC 326 ms 7692 KB
subtask1_44.txt AC 323 ms 7692 KB
subtask1_45.txt AC 333 ms 7812 KB
subtask1_46.txt AC 327 ms 7688 KB
subtask1_47.txt AC 325 ms 7692 KB
subtask1_48.txt AC 317 ms 7572 KB
subtask1_49.txt AC 326 ms 7696 KB
subtask1_50.txt AC 324 ms 7692 KB
subtask1_51.txt AC 325 ms 7688 KB
subtask1_52.txt AC 344 ms 7792 KB
subtask1_53.txt AC 332 ms 7816 KB
subtask1_54.txt AC 333 ms 7816 KB
subtask1_55.txt AC 335 ms 7692 KB
subtask1_56.txt AC 329 ms 7688 KB
subtask1_57.txt AC 327 ms 7812 KB
subtask1_58.txt AC 326 ms 7696 KB
subtask1_59.txt AC 322 ms 7692 KB