제출 #114572

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
114572		wilwxk	Shortcut (IOI16_shortcut)	C++11	31 / 100	2054 ms	504 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=1e6+5;
ll liga[MAXN], v[MAXN];
ll dp[MAXN], rdp[MAXN];
ll aux[MAXN], raux[MAXN];
ll d[MAXN];
ll respf;
int n, x;

ll testa(int a, int b, ll tam) {
	ll val=0; if(b<a) swap(a, b);
	for(int i=a; i<=b; i++) {
		for(int j=i+1; j<=b; j++) {
			ll aa=min(d[j]-d[i], tam-d[j]+d[i]);
			aa+= (i==a) ? aux[i] : v[i];
			aa+= (j==b) ? raux[j] : v[j];
			val=max(val, aa);
			// printf("   %d %d // %d %d %lld >> %lld\n", i, j, a, b, tam, val);	
		}
	}
	return val;
}

ll find_shortcut(int N, vector<int> lll, vector<int> ddd, int X)
{
	n=N; x=X;
	for(int i=2; i<=n; i++) liga[i]=lll[i-2];
	for(int i=1; i<=n; i++) v[i]=ddd[i-1];
	for(int i=1; i<=n; i++) {
		d[i]=d[i-1]+liga[i];
		dp[i]=max(dp[i-1], aux[i-1]+liga[i]+v[i]);
		aux[i]=max(aux[i-1]+liga[i], v[i]);
	}
	for(int i=n; i>=1; i--) {
		rdp[i]=max(rdp[i+1], raux[i+1]+liga[i+1]+v[i]);
		raux[i]=max(raux[i+1]+liga[i+1], v[i]);
	}
	respf=max(dp[n], rdp[1]);
    
    for(int a=1; a<=n; a++) {
    	for(int b=a+1; b<=n; b++) {
    		ll tam=d[b]-d[a]+x;
    		ll val=max(dp[a], rdp[b]);
    		val=max(val, testa(a, b, tam));
    		// printf("testa %d %d >> %lld // dp[a e b] >> %lld %lld + %lld >> val= %lld\n", a, b, tam, dp[a], rdp[b], min(d[b]-d[a], tam-d[b]+d[a]), val);
    		respf=min(respf, val);
    	}
    }

    return respf;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3