Submission #570254

#	Time	Username	Problem	Language	Result	Execution time	Memory
570254		HunterXD	Discharging (NOI20_discharging)	C++17	0 / 100	119 ms	15976 KiB

Discharging

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector <int> vi;
typedef vector <ll> vl;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector <char> vc;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vc> vvc;
typedef vector<vs> vvs;
typedef pair<ll,ll> pl;
typedef double dou;
typedef vector<pl> vpl;
typedef unsigned long long ull;
typedef uint64_t i64;
typedef vector<ull> vull;

#define f first 
#define s second 
#define pb push_back 
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define ts to_string
#define lb lower_bound 
#define ub upper_bound
#define yes cout<<'Y'<<'E'<<'S'<<endl
#define no cout<<'N'<<'O'<<endl
#define nd "\n"

void setIO(string name=""){ios_base::sync_with_stdio(0);cin.tie(0);if(sz(name)){freopen((name+".in").c_str(),"r",stdin);freopen((name+".out").c_str(),"w",stdout);}}
 
ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);}
ll mcm(ll a, ll b) {return (a * b) / gcd(a, b);}
bool prime(ll n) {for(int i=2; i<=sqrt(n); i++) if(n%i==0) return false; return true;}
struct compii{bool operator()(const ii &a, const ii &b){if(a.f==a.s)return a.s<b.s;return a.f>b.f;}};
bool comp(int a, int b) {return a>b;}
ll binpow(ll n, ll x){ll ans=1; while(x){if(x&1){ans*=n;}n*=n; x>>=1;} return ans;}

namespace operators {
template<typename T1, typename T2>istream& operator>>(istream& in, pair<T1, T2>& x){in >> x.first >> x.second;return in;}
template<typename T1, typename T2>ostream& operator<<(ostream& out, pair<T1, T2> x){out << x.first << " " << x.second;return out;}
template<typename T1>istream& operator>>(istream& in, vector<T1>& x) {for (auto& i : x) in >> i;return in;}
template<typename T1>ostream& operator<<(ostream& out, vector<T1>& x) {for (auto& i : x) out << i << " ";return out;}
template<typename T1, typename T2>ostream& operator<<(ostream& out, vector<pair <T1,T2>>& x) {for (auto& i : x) out << i.f << " "<<i.s;return out;}
template<typename T1, typename T2>istream& operator>>(istream& in, vector<pair <T1,T2>>& x) {for (auto& i : x) in >> i.f >>i.s;return in;}
}

using namespace operators;

int dx[]= {1,0,-1,0};
int dy[]= {0,1,0,-1};

const int pmod = 998244353;
const int mod = 1e9+7;
const ll inf=1e18;

ll sum(ll a, ll b){
  return (( (a+mod) %mod) + ((b+mod)%mod))%mod;
}

ll multi(ll a, ll b){
  return (((a+mod) %mod) * ((b+mod)%mod))%mod;
}

///

struct UF{
  ll n;
  vector<ll> p, range;
  vector< vector<ll>* > val;

  UF(ll m){
    n = m;
    p.assign(n, 0);
    range.assign(n, 0);
    val.assign(n, NULL);

    for(ll i = 0; i < n; i++){
      p[i] = i;
    }
  }

  ll find(ll i){
    return (p[i] == i)? i : p[i] = find(p[i]);
  }

  bool isSame(ll i, ll j){
    return (find(i) == find(j));
  }

  void unite(ll i, ll j, vector<ll>* newVal){
    if(isSame(i, j)) return;
    ll x = find(i), y = find(j);

    if(range[x] > range[y]){
      p[y] = x;
      val[x] = newVal;
      return;
    }
    
    p[x] = y;
    val[y] = newVal;
    if(range[x] == range[y]) range[y]++;
  }
};


void solve(){

  ll n;
  cin >> n;

  vector<ll> a(n+1, 0);
  vector<ll> res(n+1, inf);
  vector<pl> com;

  ll ans = 0;
  ll mx = 0;

  for(ll i = 1; i <= n; i++){
    cin >> a[i];
    mx = max(mx, a[i]);
  }

  ans = mx*n;

  if(n == 1){
    cout << a[1] << endl;
    return;
  }

  if(n == 2){
    ans = min(ans, 2*a[1] + a[2]);
    cout << ans << endl;
    return;
  }

  if(n == 3){
    ans = min(ans, 3*a[1] + 2*a[2]+ a[3]);
    ans = min(ans, 3*max(a[1], a[2]) + a[3] );
    ans = min(ans, 2*a[1] + max(a[2], a[3]) );
    cout << ans << endl;
    return;
  }


  ll actual = a[1], counter = 0;
  for(ll i = 1; i <= n; i++){
    if(a[i] > actual){
      com.pb({actual, counter});
      actual = a[i];
      counter = 1;
    }
    else{
      counter++;
    }
  }

  com.pb({actual, counter});

  pl me = com[0];
  vector<pl> com_tot;

  ll k = com.size();

  for(ll i = 1; i < k; i++){
    if( com[i].f*me.s <= me.f*(me.s+com[i].s) ){
      me.f = com[i].f;
      me.s += com[i].s;
    }
    else{
      com_tot.pb(me);
    }
  }
  com_tot.pb(me);

  ll llevo = 0;

  for(auto v: com_tot){
    ans+= v.s*(v.f+llevo);
    llevo+= v.f;
  }

  cout << ans << endl;

}

int main (){
  setIO("");
  int t=1;
  //cin >> t;
  while(t-->0) solve();
  return 0;
}

Compilation message (stderr)

Discharging.cpp: In function 'void setIO(std::string)':
Discharging.cpp:34:88: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 | void setIO(string name=""){ios_base::sync_with_stdio(0);cin.tie(0);if(sz(name)){freopen((name+".in").c_str(),"r",stdin);freopen((name+".out").c_str(),"w",stdout);}}
      |                                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Discharging.cpp:34:128: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 | void setIO(string name=""){ios_base::sync_with_stdio(0);cin.tie(0);if(sz(name)){freopen((name+".in").c_str(),"r",stdin);freopen((name+".out").c_str(),"w",stdout);}}
      |                                                                                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 11
• Subtask 5: 0 / 14
• Subtask 6: 0 / 28