Submission #126313

#	Time	Username	Problem	Language	Result	Execution time	Memory
126313		choikiwon	Sparklers (JOI17_sparklers)	C++17	50 / 100	450 ms	6592 KiB

sparklers

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MN = 100010;

void print(vector<ll> &a) {
    for(int i = 0; i < a.size(); i++) {
        cout << a[i] << ' ';
    }
    cout << endl;
}

int N, K, T;
int X[MN];
vector<ll> le, ri, psum1, psum2;

int cc[1010][1010];
int dp(int a, int b) {
    if(a == le.size() && b == ri.size()) return 1;
    int &ret = cc[a][b];
    if(ret != -1) return ret;

    ll rem = (a? psum1[a - 1] : 0) + (b? psum2[b - 1] : 0);

    ret = 0;
    if(a < le.size() && rem + le[a] >= 0) ret |= dp(a + 1, b);
    if(b < ri.size() && rem + ri[b] >= 0) ret |= dp(a, b + 1);
    return ret;
}

bool check(int x) {
    le.clear();
    ri.clear();
    for(int i = 0; i < K; i++) {
        ll d = 1LL * T * x - (X[i + 1] - X[i]);
        le.push_back(d);
    }
    reverse(le.begin(), le.end());

    for(int i = K; i < N - 1; i++) {
        ll d = 1LL * T * x - (X[i + 1] - X[i]);
        ri.push_back(d);
    }

    psum1.clear();
    psum2.clear();
    psum1.resize(le.size());
    psum2.resize(ri.size());

    for(int i = 0; i < le.size(); i++) {
        psum1[i] = le[i];
        if(i) psum1[i] += psum1[i - 1];
    }
    for(int i = 0; i < ri.size(); i++) {
        psum2[i] = ri[i];
        if(i) psum2[i] += psum2[i - 1];
    }
    memset(cc, -1, sizeof(cc));
    return dp(0, 0);
}

int main() {
    scanf("%d %d %d", &N, &K, &T);
    K--;

    for(int i = 0; i < N; i++) {
        scanf("%d", &X[i]);
    }

    int s = 0, e = 1e9 / T + 1, p = -1;
    while(s <= e) {
        int m = (s + e)>>1;

        if(check(2 * m)) {
            p = m;
            e = m - 1;
        }
        else s = m + 1;
    }
    printf("%d", p);
}

Compilation message (stderr)

sparklers.cpp: In function 'void print(std::vector<long long int>&)':
sparklers.cpp:9:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < a.size(); i++) {
                    ~~^~~~~~~~~~
sparklers.cpp: In function 'int dp(int, int)':
sparklers.cpp:21:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(a == le.size() && b == ri.size()) return 1;
        ~~^~~~~~~~~~~~
sparklers.cpp:21:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(a == le.size() && b == ri.size()) return 1;
                          ~~^~~~~~~~~~~~
sparklers.cpp:28:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(a < le.size() && rem + le[a] >= 0) ret |= dp(a + 1, b);
        ~~^~~~~~~~~~~
sparklers.cpp:29:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(b < ri.size() && rem + ri[b] >= 0) ret |= dp(a, b + 1);
        ~~^~~~~~~~~~~
sparklers.cpp: In function 'bool check(int)':
sparklers.cpp:52:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < le.size(); i++) {
                    ~~^~~~~~~~~~~
sparklers.cpp:56:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ri.size(); i++) {
                    ~~^~~~~~~~~~~
sparklers.cpp: In function 'int main()':
sparklers.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &N, &K, &T);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &X[i]);
         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 50