Submission #57955

#	Time	Username	Problem	Language	Result	Execution time	Memory
57955		BrunoPloumhans	Semiexpress (JOI17_semiexpress)	C++14	0 / 100	3 ms	944 KiB

semiexpress

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

#define int long long
#define D(x) //cout << #x << ": " << x << endl

template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "{ ";
  for(const T& t : v)
    os << t << ", ";
  return os << "}";
}

template<typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& v) {
  return os << "{ " << v.first << ", " << v.second << " }";
}

int n, M, K;
int A, B, C;
int T;

vector<int> express;
vector<vector<pair<int, int>>> impr;

int dp[3001][3001];

void solve(int k, int l, int r, int i, int j) {
  //cout << "solve(" << k << ", " << l << ", " << r << ", " << i << ", " << j << ")\n";
  if(l > r) return;
  int mid = (l+r)/2;
  int best = -1;
  dp[k][mid] = -1;
  for(int x = i; x <= min(j, mid); ++x) {
    int nc = dp[k+1][mid-x] + impr[k][x].second;
    if(nc >= dp[k][mid]) {
      best = x;
      dp[k][mid] = nc;
    }
  }
  if(l == r) {
    return;
  }
  solve(k, l, mid-1, i, /*best*/j);
  solve(k, mid+1, r, /*best*/i, j);
}

int time(int p1, int p2, int p3) {
  return p1*B + (p2-p1)*C + (p3-p2)*A;
}

signed main() {
  ios_base::sync_with_stdio(false);

  cin >> n >> M >> K >> A >> B >> C >> T;
  K -= M;

  impr.resize(M);
  express.resize(M);
  for(int i = 0; i < M; ++i) {
    cin >> express[i];
    --express[i];
    impr[i].push_back({express[i], (express[i]*B <= T)});
  }

  for(int seg = 0; seg < M-1; ++seg) {
    int pos = express[seg]+1;
    while(pos < express[seg+1] && impr[seg].size() <= K) {
      int timeToPos = time(express[seg], impr[seg].back().first, pos);
      if(timeToPos <= T) {
	++impr[seg].back().second;
      } else if(time(express[seg], pos, pos) <= T) {
	impr[seg].push_back({pos, pos - express[seg]+1});
      }
      ++pos;
    }
  }

  D(impr);

  for(int i = 0; i <= K; ++i) {
    dp[M-1][i] = impr[M-1][0].second;
  }

  for(int i = M-2; i >= 0; --i) {
    solve(i, 0, K, 0, impr[i].size()-1);
  }

  cout << dp[0][K]-1 << endl;

  /*for(int i = 0; i < M; ++i) {
    for(int j = 0; j <= K; ++j) {
      cout << dp[i][j] << " ";
    }
    cout << endl;
    }*/

  return 0;
}

Compilation message (stderr)

semiexpress.cpp: In function 'void solve(long long int, long long int, long long int, long long int, long long int)':
semiexpress.cpp:33:7: warning: variable 'best' set but not used [-Wunused-but-set-variable]
   int best = -1;
       ^~~~
semiexpress.cpp: In function 'int main()':
semiexpress.cpp:69:52: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pos < express[seg+1] && impr[seg].size() <= K) {
                                   ~~~~~~~~~~~~~~~~~^~~~

• Subtask 1: 0 / 18
• Subtask 2: 0 / 30
• Subtask 3: 0 / 52