Submission #480736

#	Time	Username	Problem	Language	Result	Execution time	Memory
480736		Mackerel_Pike	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	16 ms	332 KiB

semiexpress

#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 (stderr)

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 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52