Submission #1208169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208169		nguyn	Candies (JOI18_candies)	C++20	100 / 100	80 ms	11440 KiB

candies

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

#define int long long
#define ll long long 
#define F first
#define S second
#define pb push_back 
#define pii pair<int,int>

const int N = 2e5 + 5;

int vis[N];
int a[N], n;
int l[N], r[N];

signed main(){
    ios_base::sync_with_stdio(false) ; 
    cin.tie(0) ; cout.tie(0) ; 
    if (fopen("INP.INP" ,"r")) {
        freopen("INP.INP" ,"r" , stdin) ;
        freopen("OUT.OUT" , "w" , stdout) ;
    }
    cin >> n; 
    for (int i = 1; i <= n; i++) {
    	cin >> a[i];
    	l[i] = i - 1;
    	r[i] = i + 1; 
    }
    a[0] = a[n + 1] = -1e18;
    priority_queue<pii> pq;
    for (int i = 1; i <= n; i++) {
    	pq.push({a[i], i});
    }
    int res = 0;
    for (int i = 1; i <= (n + 1) / 2; i++) {
    	bool ok = 0; 
    	while(!pq.empty() && !ok) {
    		pii cur = pq.top(); 
    		pq.pop();
    		if (vis[cur.S]) continue;
    		ok = 1;
    		res += cur.F;
    		int lef = l[cur.S];
    		int rig = r[cur.S]; 
    		a[cur.S] = a[lef] + a[rig] - a[cur.S]; 
    		vis[lef] = vis[rig] = 1;
    		l[cur.S] = l[l[cur.S]]; 
    		r[cur.S] = r[r[cur.S]];
    		l[r[cur.S]] = cur.S;
    		r[l[cur.S]] = cur.S;
    		pq.push({a[cur.S], cur.S});
    	}
    	cout << res << '\n';
    }
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen("INP.INP" ,"r" , stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
candies.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen("OUT.OUT" , "w" , stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92