답안 #95242 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95242	2019-01-29T00:46:56 Z	updown1	Salesman (IOI09_salesman)	C++17	70 / 100	1000 ms	49828 KB

salesman

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, N)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
//500,000,000 operations
const int MAXN = 500003, INF = 2*1e9;
//Global Variables
int N, U, D, S, dp[MAXN], t0D[4*MAXN+1], t0U[4*MAXN+1], dpU[4*MAXN+1], dpD[4*MAXN+1], pre[MAXN];
pair<int, pair<int, int> > fairs[MAXN]; /// (day, (location, profit) )

void updatedpU(int ind, int L, int R, int x, int v) {
    if (x < L || R < x) return;
    if (L == R) {
        dpU[ind] = v;
        return;
    }
    updatedpU(ind*2, L, (L+R)/2, x, v);
    updatedpU(ind*2+1, (L+R)/2+1, R, x, v);
    dpU[ind] = max(dpU[ind*2], dpU[ind*2+1]);
}
void updatedpD(int ind, int L, int R, int x, int v) {
    if (x < L || R < x) return;
    if (L == R) {
        dpD[ind] = v;
        return;
    }
    updatedpD(ind*2, L, (L+R)/2, x, v);
    updatedpD(ind*2+1, (L+R)/2+1, R, x, v);
    dpD[ind] = max(dpD[ind*2], dpD[ind*2+1]);
}
void updatet0D(int ind, int L, int R, int x, int v) {
    if (x < L || R < x) return;
    if (L == R) {
        t0D[ind] = v;
        return;
    }
    updatet0D(ind*2, L, (L+R)/2, x, v);
    updatet0D(ind*2+1, (L+R)/2+1, R, x, v);
    t0D[ind] = max(t0D[ind*2], t0D[ind*2+1]);
}
void updatet0U(int ind, int L, int R, int x, int v) {
    if (x < L || R < x) return;
    if (L == R) {
        t0U[ind] = v;
        return;
    }
    updatet0U(ind*2, L, (L+R)/2, x, v);
    updatet0U(ind*2+1, (L+R)/2+1, R, x, v);
    t0U[ind] = max(t0U[ind*2], t0U[ind*2+1]);
}

int querydpU(int ind, int L, int R, int oL, int oR) {
    if (oR < L || R < oL) return -INF;
    if (oL == 6 && oR == 6) w<< ind s L s R c dpU[ind]<<e;
    if (oL <= L && R <= oR) return dpU[ind];
    return max(querydpU(ind*2, L, (L+R)/2, oL, oR), querydpU(ind*2+1, (L+R)/2+1, R, oL, oR));
}
int querydpD(int ind, int L, int R, int oL, int oR) {
    if (oR < L || R < oL) return -INF;
    if (oL <= L && R <= oR) return dpD[ind];
    return max(querydpD(ind*2, L, (L+R)/2, oL, oR), querydpD(ind*2+1, (L+R)/2+1, R, oL, oR));
}
int queryt0U(int ind, int L, int R, int oL, int oR) {
    if (oR < L || R < oL) return -INF;
    if (oL <= L && R <= oR) return t0U[ind];
    return max(queryt0U(ind*2, L, (L+R)/2, oL, oR), queryt0U(ind*2+1, (L+R)/2+1, R, oL, oR));
}
int queryt0D(int ind, int L, int R, int oL, int oR) {
    if (oR < L || R < oL) return -INF;
    if (oL <= L && R <= oR) return t0D[ind];
    return max(queryt0D(ind*2, L, (L+R)/2, oL, oR), queryt0D(ind*2+1, (L+R)/2+1, R, oL, oR));
}

main() {
    //ifstream cin("test.in");
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> U >> D >> S;
    ffi cin >> fairs[i].a >> fairs[i].b.a >> fairs[i].b.b;
    fairs[N] = mp(MAXN, mp(S, 0));
    N++;
    sort(fairs, fairs+N);
    For (i, 0, MAXN) dp[i] = -INF;
    For (i, 0, 4*MAXN+1) t0D[i] = t0U[i] = dpU[i] = dpD[i] = -INF;
    dp[S] = 0;
    updatedpU(1, 0, MAXN-1, S, -U*S);
    updatedpD(1, 0, MAXN-1, S, D*S);
    //w<< querydpU(1, 0, MAXN-1, 0, MAXN-1)<<e;
    int i=0;
    while (i < N) {
        int k = i;
        while (k+1 < N && fairs[k+1].a == fairs[i].a) k++;
        /// fairs with the same day are i to k
        /// update with pre values
        if (i != 0) pre[i-1] = 0;
        pre[i] = fairs[i].b.b;
        For (l, i+1, k+1) pre[l] = pre[l-1] + fairs[l].b.b;
        For (l, i, k+1) {
            int loc = fairs[l].b.a;
            int prel1 = 0;
            if (l != 0) prel1 = pre[l-1];
            int tdp0 = max(querydpU(1, 0, MAXN-1, loc, MAXN-1) + U*loc, querydpD(1, 0, MAXN-1, 0, loc) - D*loc);
            //w<< loc s tdp0 c tdp0 + D*loc-prel1 s tdp0 - U*loc + pre[l]<<e;
            //if (loc == S) w<<"at S" s querydpU(1, 0, MAXN-1, 6, 6) s tdp0<<e;
            updatet0D(1, 0, MAXN-1, loc, tdp0 + D*loc-prel1);
            updatet0U(1, 0, MAXN-1, loc, tdp0 - U*loc + pre[l]);
        }
        For (l, i, k+1) {
            int loc = fairs[l].b.a;
            int prel1 = 0;
            if (l != 0) prel1 = pre[l-1];
            dp[loc] = max(queryt0D(1, 0, MAXN-1, 0, loc) + pre[l] - D*loc, queryt0U(1, 0, MAXN-1, loc, MAXN-1) - prel1+ U*loc);
            //w<< "dp" s loc s dp[loc] c queryt0D(1, 0, MAXN-1, 0, loc)<<e;
            //if (loc == 6) w<< dp[loc]<<e;
            updatedpU(1, 0, MAXN-1, loc, dp[loc]-U*loc);
            //if (loc == 6) w<< dp[loc] s querydpU(1, 0, MAXN-1, S, MAXN-1)<<e;
            updatedpD(1, 0, MAXN-1, loc, dp[loc]+D*loc);
        }
        /// reset values
        For (l, i, k+1) {
            int loc = fairs[l].b.a;
            updatet0D(1, 0, MAXN-1, loc, -INF);
            updatet0U(1, 0, MAXN-1, loc, -INF);
        }
        i = k+1;
    }
    //For (i, 0, MAXN) if (dp[i] != -INF) w<< i c dp[i]<<e;
    w << dp[S]<<e;
}

Compilation message

salesman.cpp:86:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
70.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	33656 KB	Output is correct
2	Correct	26 ms	33656 KB	Output is correct
3	Correct	27 ms	33656 KB	Output is correct
4	Correct	30 ms	33656 KB	Output is correct
5	Correct	37 ms	33784 KB	Output is correct
6	Correct	84 ms	34296 KB	Output is correct
7	Correct	186 ms	35420 KB	Output is correct
8	Correct	355 ms	37080 KB	Output is correct
9	Correct	505 ms	38452 KB	Output is correct
10	Correct	859 ms	43180 KB	Output is correct
11	Correct	986 ms	43768 KB	Output is correct
12	Execution timed out	1074 ms	45760 KB	Time limit exceeded
13	Execution timed out	1082 ms	46300 KB	Time limit exceeded
14	Execution timed out	1081 ms	49828 KB	Time limit exceeded
15	Execution timed out	1084 ms	49272 KB	Time limit exceeded
16	Execution timed out	1085 ms	48820 KB	Time limit exceeded
17	Correct	26 ms	33656 KB	Output is correct
18	Correct	27 ms	33656 KB	Output is correct
19	Correct	28 ms	33656 KB	Output is correct
20	Correct	31 ms	33784 KB	Output is correct
21	Correct	37 ms	33704 KB	Output is correct
22	Correct	36 ms	33724 KB	Output is correct
23	Correct	36 ms	33784 KB	Output is correct
24	Correct	37 ms	33656 KB	Output is correct
25	Correct	294 ms	36608 KB	Output is correct
26	Correct	554 ms	39672 KB	Output is correct
27	Correct	975 ms	43640 KB	Output is correct
28	Execution timed out	1082 ms	44404 KB	Time limit exceeded
29	Execution timed out	1067 ms	47224 KB	Time limit exceeded
30	Execution timed out	1074 ms	48536 KB	Time limit exceeded

답안 #95242

Compilation message

Subtask #1 70.0 / 100.0

Subtask #1
70.0 / 100.0