Submission #291676

#	Time	Username	Problem	Language	Result	Execution time	Memory
291676		crossing0ver	Discharging (NOI20_discharging)	C++17	9 / 100	1084 ms	10712 KiB

Discharging

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

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 / 9
• Subtask 2: 0 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 11
• Subtask 5: 0 / 14
• Subtask 6: 0 / 28