oj.uz

답안 #221859

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
221859 2020-04-11T10:26:28 Z lyc 휴가 (IOI14_holiday) C++14
100 / 100
 1433 ms 9040 KB 
#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;

#define SZ(x) ((int)(x).size())
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)

long long solve(int n, int s, int d, int a[]) {
    long long lt[d+1], rt[d+1];
    int lo[d+1], ro[d+1];

    lt[0] = rt[0] = 0;

    RFOR(k,17,0){
        priority_queue<int,vector<int>,greater<int>> incl;
        priority_queue<int> excl;
        int ep = s+1;
        long long cur = 0;
        for (int x = 1<<k; x <= d; x += 1<<(k+1)) {
            int lim = (x+(1<<k) <= d ? lo[x+(1<<k)] : 0);
            while (!excl.empty() && SZ(incl) + 2*(s-ep) < x) {
                int v = excl.top(); excl.pop();
                cur += v; incl.push(v);
            }
            lt[x] = cur, lo[x] = ep;
            while (ep > lim) {
                --ep;
                cur += a[ep]; incl.push(a[ep]);
                while (!incl.empty() && SZ(incl) + 2*(s-ep) > x) {
                    int v = incl.top(); incl.pop();
                    cur -= v; excl.push(v);
                }
                if (cur > lt[x]) lt[x] = cur, lo[x] = ep;
            }
        }
    }

    RFOR(k,17,0){
        priority_queue<int,vector<int>,greater<int>> incl;
        priority_queue<int> excl;
        int ep = s;
        long long cur = 0;
        for (int x = 1<<k; x <= d; x += 1<<(k+1)) {
            int lim = (x+(1<<k) <= d ? ro[x+(1<<k)] : n-1);
            while (!excl.empty() && SZ(incl) + (ep-s) < x) {
                int v = excl.top(); excl.pop();
                cur += v; incl.push(v);
            }
            rt[x] = cur, ro[x] = ep;
            while (ep < lim) {
                ++ep;
                cur += a[ep]; incl.push(a[ep]);
                while (!incl.empty() && SZ(incl) + (ep-s) > x) {
                    int v = incl.top(); incl.pop();
                    cur -= v; excl.push(v);
                }
                if (cur > rt[x]) rt[x] = cur, ro[x] = ep;
            }
        }
    }

    //FOR(x,0,d) { cout << x << " :: " << lt[x] << ' ' << rt[x] << endl; }
    //cout << endl;

    long long ans = 0;
    FOR(x,0,d) ans = max(ans, lt[x]+rt[d-x]);
    return ans;
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    long long ans = solve(n,start,d,attraction);
    reverse(attraction,attraction+n);
    ans = max(ans, solve(n,n-1-start,d,attraction));
    return ans;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 5 ms 384 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 231 ms 7220 KB Output is correct
2 Correct 55 ms 6828 KB Output is correct
3 Correct 258 ms 7152 KB Output is correct
4 Correct 57 ms 6880 KB Output is correct
5 Correct 948 ms 5428 KB Output is correct
6 Correct 407 ms 5240 KB Output is correct
7 Correct 569 ms 3380 KB Output is correct
8 Correct 564 ms 3564 KB Output is correct
9 Correct 284 ms 6412 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 640 KB Output is correct
2 Correct 9 ms 640 KB Output is correct
3 Correct 16 ms 640 KB Output is correct
4 Correct 25 ms 512 KB Output is correct
5 Correct 22 ms 512 KB Output is correct
6 Correct 8 ms 384 KB Output is correct
7 Correct 7 ms 384 KB Output is correct
8 Correct 7 ms 384 KB Output is correct
9 Correct 8 ms 384 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 279 ms 8776 KB Output is correct
2 Correct 1433 ms 9040 KB Output is correct
3 Correct 117 ms 1456 KB Output is correct
4 Correct 14 ms 384 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 7 ms 384 KB Output is correct
7 Correct 8 ms 384 KB Output is correct
8 Correct 725 ms 3348 KB Output is correct
9 Correct 732 ms 3348 KB Output is correct