oj.uz

Submission #72834

# Submission time Handle Problem Language Result Execution time Memory
72834 2018-08-27T04:06:54 Z tlwpdus Nectar with Coconut Jelly (FXCUP3_nectar) C++11
15 / 100
 2000 ms 282196 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

ll n, j, r, t;
ll whe[100100];
ll rem[100100];
ll arr[100100];
ll pre[100100];
ll INF = 1e9;
vector<int> lis[300100];

ll divi(ll a, ll b) {return (a+b-1)/b;}
ll tim(int idx) {
    return arr[idx]==arr[idx-1]?INF:divi(rem[idx]-(arr[idx]-1)*r,arr[idx]-arr[idx-1]);
}

void upd(int idx, ll cur) {
    rem[idx] -= (arr[idx]-pre[idx-1])*(cur-whe[idx]);
    whe[idx] = cur;
    if (tim(idx)+cur<=t) {
        //printf("%lld : %d\n",tim(idx)+cur,idx);
        lis[tim(idx)+cur].push_back(idx);
    }
}

ll tmp[100100];
int main() {
    int i;

    scanf("%lld%lld%lld%lld",&n,&j,&r,&t);
    for (i=1;i<=n;i++) rem[i] = j, pre[i] = arr[i] = divi(j,r);
    lis[tim(1)].push_back(1);
    for (i=1;i<=t;i++) {
        //printf("%d!\n",i);
        for (int j=0;j<lis[i].size();j++) {
            int v = lis[i][j];
            //printf(" %d!\n",v);
            rem[v] -= (arr[v]-pre[v-1])*(i-whe[v]);
            whe[v] = i;
            //printf("%d, %lld!\n",v,rem[v]);
            if (arr[v]!=divi(rem[v],r)) {
                arr[v] = divi(rem[v],r);
                upd(v,i);
                if (v!=n) upd(v+1,i);
            }
        }
        for (int &v : lis[i]) {
            pre[v] = arr[v];
        }
    }
    ll sum = j*n;
    for (i=1;i<n;i++) {
        sum -=rem[i]-(arr[i]-arr[i-1])*(t-whe[i]);
        printf("%lld\n",rem[i]-(arr[i]-arr[i-1])*(t-whe[i]));
    }
    printf("%lld\n",sum);

    return 0;
}

Compilation message

nectar.cpp: In function 'int main()':
nectar.cpp:40:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0;j<lis[i].size();j++) {
                      ~^~~~~~~~~~~~~~
nectar.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld%lld%lld",&n,&j,&r,&t);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 9 ms 7432 KB Output is correct
4 Correct 8 ms 7508 KB Output is correct
5 Correct 8 ms 7636 KB Output is correct
6 Correct 8 ms 7792 KB Output is correct
7 Correct 10 ms 7792 KB Output is correct
8 Correct 31 ms 9076 KB Output is correct
9 Correct 9 ms 9076 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 9 ms 7432 KB Output is correct
4 Correct 8 ms 7508 KB Output is correct
5 Correct 8 ms 7636 KB Output is correct
6 Correct 8 ms 7792 KB Output is correct
7 Correct 10 ms 7792 KB Output is correct
8 Correct 31 ms 9076 KB Output is correct
9 Correct 9 ms 9076 KB Output is correct
10 Correct 9 ms 9076 KB Output is correct
11 Correct 18 ms 9268 KB Output is correct
12 Correct 38 ms 11336 KB Output is correct
13 Correct 33 ms 11340 KB Output is correct
14 Correct 32 ms 13152 KB Output is correct
15 Correct 21 ms 13152 KB Output is correct
16 Correct 43 ms 13152 KB Output is correct
17 Execution timed out 2089 ms 282196 KB Time limit exceeded
18 Halted 0 ms 0 KB -