Submission #1356472
Source Code Expand
#include <iostream>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define GREY 2
#define WHITE 1
#define BLACK 0
ll maximum=-1,d, k, tenki[20001], maxi[20000] = { -1 }, mini[20001], dp[2][201] = { -1 }, go = 0;
ll DP(ll n, ll previous,ll mai) {
if (n == d) { return 0; }
if (n == 0) {
return max(DP(n + 1, maxi[tenki[n]], 0), DP(n + 1, mini[tenki[n]], 1));
}
if (dp[mai][n]>=0) { return dp[mai][n]; }
return dp[mai][n]=max(DP(n + 1, maxi[tenki[n]], 0)+abs(previous - maxi[tenki[n]]),DP(n + 1, mini[tenki[n]],1)+abs(previous - mini[tenki[n]]));
}
int main()
{
REP(i, 2) {
REP(j, 201) { dp[i][j] = -1; }
}
memset(maxi, -1, sizeof(maxi));
REP(i, 20001) { mini[i] = 100000; }
cin >> d >> k;
REP(i, d) {
cin >> tenki[i];
}
REP(i, k) {
ll mi, ma, c;
cin >> mi >> ma >> c;
FOR(j, mi, ma + 1) {
maxi[j] = max(maxi[j], c);
mini[j] = min(mini[j], c);
}
}
cout <<DP(0, 0,0) << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 暑い日々 (Hot days) |
User |
keidaroo |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
1130 Byte |
Status |
AC |
Exec Time |
1 ms |
Memory |
512 KB |
Judge Result
Set Name |
set01 |
set02 |
set03 |
set04 |
set05 |
Score / Max Score |
20 / 20 |
20 / 20 |
20 / 20 |
20 / 20 |
20 / 20 |
Status |
|
|
|
|
|
Set Name |
Test Cases |
set01 |
data1 |
set02 |
data2 |
set03 |
data3 |
set04 |
data4 |
set05 |
data5 |
Case Name |
Status |
Exec Time |
Memory |
data1 |
AC |
1 ms |
512 KB |
data2 |
AC |
1 ms |
512 KB |
data3 |
AC |
1 ms |
512 KB |
data4 |
AC |
1 ms |
512 KB |
data5 |
AC |
1 ms |
512 KB |