oj.uz

Submission #480736

# Submission time Handle Problem Language Result Execution time Memory
480736 2021-10-18T02:06:24 Z Mackerel_Pike Semiexpress (JOI17_semiexpress) C++14
100 / 100
 16 ms 332 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 3005;

int n, m, k, a, b, c, ans = 0;
int s[maxn], p[maxn];
long long T;
long long t[maxn];

int main(){
  scanf("%d%d%d", &n, &m, &k);
  scanf("%d%d%d", &a, &b, &c);
  scanf("%lld", &T);
  for(int i = 0; i < m; ++i)
    scanf("%d", s + i), --s[i];
  s[m] = n;

  for(int i = 0; i < m; ++i){
    t[i] = 1ll * s[i] * b; p[i] = s[i];
    long long res = (T - t[i]) / a + 1;
    if(t[i] > T)
      continue;
    ans += min(1ll * s[i + 1] - p[i], res);
    p[i] = min(1ll * s[i + 1], p[i] + res);
    t[i] = 1ll * (p[i] - s[i]) * c + 1ll * s[i] * b;
  }
  k -= m;

  for(int i = 0; i < k; ++i){
    int pos = -1;
    for(int j = 0; j < m - 1; ++j){
      if(t[j] <= T &&
	 (!~pos ||
	  min(1ll * s[j + 1] - p[j], (T - t[j]) / a + 1) > min(1ll * s[pos + 1] - p[pos], (T - t[pos]) / a + 1)))
	pos = j;
    }
    if(!~pos)
      break;
    int res = min(1ll * s[pos + 1] - p[pos], (T - t[pos]) / a + 1);
    ans += res;
    p[pos] += res;
    t[pos] = 1ll * (p[pos] - s[pos]) * c + 1ll * s[pos] * b;
  }

  printf("%d\n", ans - 1);
  return 0;
}

Compilation message

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   scanf("%d%d%d", &n, &m, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   scanf("%d%d%d", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf("%lld", &T);
      |   ~~~~~^~~~~~~~~~~~
semiexpress.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%d", s + i), --s[i];
      |     ~~~~~^~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 292 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 292 KB Output is correct
19 Correct 3 ms 332 KB Output is correct
20 Correct 6 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 16 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 5 ms 204 KB Output is correct
30 Correct 3 ms 204 KB Output is correct