oj.uz

Submission #72420

# Submission time Handle Problem Language Result Execution time Memory
72420 2018-08-26T08:01:21 Z 마릴린 희정(#2180, gs14004, ho94949) Nectar with Coconut Jelly (FXCUP3_nectar) C++17
15 / 100
 2000 ms 624 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXK = 300;
int J, R, T;
pair<int, vector<int> > solve(vector<int> V)
{
  int v = J;
  int t = 0;
  int plusdv = MAXK+1;
  vector<int> initial(MAXK+2, -1); initial[0] = -1;
  while(t < T)
  {
    while (plusdv > 0 && V[plusdv-1] <= t) --plusdv;
    
    
    
    int minusdv = (v+R-1)/R;
    int dv = minusdv-plusdv; 

    //[t, T) => minusdv
    if(initial[minusdv] == -1)
      initial[minusdv] = t;

    
    
    int EV_end_event = T;

    // v - k * dv <= (minusdv-1)*R
    // k >= (v-(minusdv-1)*R)/dv    
    if(dv != 0)
      EV_end_event = min(EV_end_event, t + (v-(minusdv-1)*R + dv-1)/dv);
    
    if(plusdv != 0)
      EV_end_event = min(EV_end_event, V[plusdv-1]);
    
    EV_end_event = t+1;
    //printf("%d %d %d %d\n", t, v, minusdv, plusdv);

    v -= dv*(EV_end_event-t);
    t = EV_end_event;
  }
  if(initial[0] == -1) initial[0] = T;
  for(int i=0; i<=MAXK; ++i)
  {
    if(initial[i] == 0) break;
    if(initial[i+1] == -1) initial[i+1] = initial[i];
  }
  return make_pair(v, initial);
}
int main()
{
  int N;
  scanf("%d%d%d%d", &N, &J, &R, &T);
  vector<int> initial(MAXK+2, -1);
  initial[0] = 0;
  long long v = 1LL*N*J;
  for(int i=0; i<N-1; ++i)
  {
    int ans;
    tie(ans, initial) = solve(initial);
    //for(int i=0; i<10; ++i){int x=initial[i]; printf("%d " ,x);}
    //puts("");
    printf("%d\n", ans);
    v -= ans;
  }
  printf("%lld\n", v);
  return 0;
}

Compilation message

nectar.cpp: In function 'int main()':
nectar.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &N, &J, &R, &T);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 4 ms 356 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 3 ms 516 KB Output is correct
6 Correct 5 ms 516 KB Output is correct
7 Correct 28 ms 516 KB Output is correct
8 Correct 43 ms 516 KB Output is correct
9 Correct 46 ms 592 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 4 ms 356 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 3 ms 516 KB Output is correct
6 Correct 5 ms 516 KB Output is correct
7 Correct 28 ms 516 KB Output is correct
8 Correct 43 ms 516 KB Output is correct
9 Correct 46 ms 592 KB Output is correct
10 Execution timed out 2033 ms 624 KB Time limit exceeded
11 Halted 0 ms 0 KB -