oj.uz

Submission #199248

# Submission time Handle Problem Language Result Execution time Memory
199248 2020-01-30T16:32:47 Z Mercenary Semiexpress (JOI17_semiexpress) C++14
100 / 100
 26 ms 11384 KB 
#include<bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
const int maxn = 3e3 + 5;
const int mod = 1e9 + 7;
int n , m,k;
int sm , lc , ep;
ll T;
int dp[maxn][maxn] , cur[maxn];
int Cal(int x , int len , ll T){
    if(T < lc)return x;
    return min((ll)len , x + T / lc);
}
void Cal(int val[maxn] , int len , ll T){
    if(T < 0)return;
    int cur = 1;
    for(int i = 0 ; i <= k ; ++i){
        cur = val[i] = Cal(cur, len , T - (ll)(cur - 1) * sm);
        if((ll)(min(len , cur + 1) - 1) * sm <= T)cur = min(cur + 1 , len);
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n >> m >> k >> lc >> ep >> sm >> T;
    vector<int> val(m);k -= m;
    for(auto & c : val)cin >> c;val.pb(n + 1);
    priority_queue<ii> pq;
    int res = 0;
    for(int i = 0 ; i < m ; ++i){
        Cal(dp[i],val[i + 1] - val[i] , T - (ll)ep * (val[i] - 1));
        res += dp[i][0];
        pq.push(mp(dp[i][1] - dp[i][0],i));
//        for(int j = 0 ; j <= k; ++j)cout << dp[i][j] << " ";cout << endl;
    }
    while(k--){
        auto u = pq.top();pq.pop();
        res += u.first;
        cur[u.second]++;
        pq.push(mp(dp[u.second][cur[u.second]+ 1]-dp[u.second][cur[u.second]],u.second));
    }
    cout << res - 1;
}

Compilation message

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:40:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(auto & c : val)cin >> c;val.pb(n + 1);
     ^~~
semiexpress.cpp:40:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(auto & c : val)cin >> c;val.pb(n + 1);
                                 ^~~
semiexpress.cpp:35:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:36:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 248 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 504 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 248 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 5 ms 424 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 504 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 248 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 5 ms 424 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 504 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 9 ms 2040 KB Output is correct
20 Correct 10 ms 2168 KB Output is correct
21 Correct 6 ms 888 KB Output is correct
22 Correct 8 ms 1400 KB Output is correct
23 Correct 26 ms 11384 KB Output is correct
24 Correct 8 ms 5368 KB Output is correct
25 Correct 6 ms 376 KB Output is correct
26 Correct 10 ms 8184 KB Output is correct
27 Correct 8 ms 6392 KB Output is correct
28 Correct 8 ms 6392 KB Output is correct
29 Correct 11 ms 3576 KB Output is correct
30 Correct 8 ms 1404 KB Output is correct