第12回日本情報オリンピック 予選(オンライン)

Submission #1356472

Source codeソースコード

#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

Task問題 D - 暑い日々 (Hot days)
User nameユーザ名 keidaroo
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1130 Byte
File nameファイル名
Exec time実行時間 1 ms
Memory usageメモリ使用量 512 KB

Test case

Set

Set name Score得点 / Max score Cases
set01 20 / 20 data1
set02 20 / 20 data2
set03 20 / 20 data3
set04 20 / 20 data4
set05 20 / 20 data5

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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