oj.uz

Submission #291677

# Submission time Handle Problem Language Result Execution time Memory
291677 2020-09-05T16:11:46 Z crossing0ver Discharging (NOI20_discharging) C++17
22 / 100
 1000 ms 13600 KB 
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define vi vector<int>
using namespace std;
const int N = 1e6+6;
//ll ans;
int n,arr[N],M;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void RAND() {
    int ANS = 100000000000;
    int M;
    for (int mask = 1; mask < (1<<n); mask++) {
        if ((mask & (1 << (n-1))) == 0) continue;
        int k = 0,last = 0,A = 0;
        for (int j = 0; j < n; j++) {
            if ( ((1<<j) & mask) == 0) continue;
            int mx = 0;
            for (int z = last; z <= j;z++)
                    mx = max(mx,arr[z+1]);
            k += mx;
            A += (j - last + 1)*k;
            last = j + 1;
        }
        if (A < ANS) {
            M = mask;

        }
        ANS = min(ANS,A);


    }
    //cout << 1 <<

   // cout << "REAL : " << ANS<<'\n';
    // <<"  OURS : ";
    //for (int i = 0; i < n; i++)
     //   if ((1<< i) & M) cout << i+1 << ' ';
   // cout <<
  // cout << endl;
  cout << ANS;
  exit(0);
//1 8 17 7 19 2 11 3 15 13
//REAL : 181  OURS : 190


}
int dp[N];
main(){

  //  for (int h = 1; h <= t; h++) {
         //   n = rng()%10 + 1;
   cin >> n;
   //RAND();
    int tot = n;
    for (int i = 1; i <= n; i++) {
          // arr[i] = rng()%20 + 1;
           // cout << arr[i] <<' ';
            cin >> arr[i];
    }cout <<'\n';if (n <= 20) RAND();

    for (int i = 1; i <= n; i++) {
        dp[i] = 1000000000000000;
        for (int j = 1; j <= i; j++)
            dp[i] = min(dp[i],dp[j-1] + (n - j + 1)*arr[i]);
    }
    cout << dp[n];
    exit(0);/*
    for (int i = 1; i <= n;i++)

    ll ans = 0;
    int mx = 0,k = 0,block = 0;
    for (int i = 1; i <= n; i++) {
          //  block++;
        if (tot*mx <= block*arr[i]) {
         //       cout <<i <<' '<<ans<<'\n';
            block = 0;
            k += arr[i];
            tot = n - i+1;
            ans += k;
        }
        else {
            if (mx < arr[i]) {
            //    cout << i <<'
                    //ans += k;
                    ans += (arr[i] - mx)*(block);
                    //ans += mx;
                    k += arr[i] - mx;
                    ans+=k;
                    mx = arr[i];
                    }
            else ans += k;

       // if (mx < arr[i]) mx = arr[i], k += arr[i] - mx;
        }
        mx = max(mx,arr[i]);
     //  ans += k;
        block++;
    }
    cout << ans <<'\n';
   // }*/

}

Compilation message

Discharging.cpp: In function 'void RAND()':
Discharging.cpp:15:9: warning: variable 'M' set but not used [-Wunused-but-set-variable]
   15 |     int M;
      |         ^
Discharging.cpp: At global scope:
Discharging.cpp:52:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   52 | main(){
      |      ^
Discharging.cpp: In function 'int main()':
Discharging.cpp:58:9: warning: unused variable 'tot' [-Wunused-variable]
   58 |     int tot = n;
      |         ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 400 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 400 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Execution timed out 1084 ms 13600 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 8356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 512 KB Output is correct
21 Correct 3 ms 384 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 3 ms 384 KB Output is correct
24 Correct 3 ms 384 KB Output is correct
25 Correct 3 ms 400 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 3 ms 384 KB Output is correct
28 Correct 3 ms 384 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Incorrect 3 ms 384 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #6
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 512 KB Output is correct
21 Correct 3 ms 384 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 3 ms 384 KB Output is correct
24 Correct 3 ms 384 KB Output is correct
25 Correct 3 ms 400 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 3 ms 384 KB Output is correct
28 Correct 3 ms 384 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Execution timed out 1084 ms 13600 KB Time limit exceeded
31 Halted 0 ms 0 KB -