oj.uz

답안 #236170

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
236170 2020-05-31T10:41:07 Z rajarshi_basu Candies (JOI18_candies) C++14
0 / 100
 8 ms 640 KB 
#include <stdio.h>     
#include <stdlib.h>    
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long 
#define ld long double
//#define int short
#define vi vector<int>
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define iii pair<ll,ii>
#define pll pair<ll,ll>
#define plll pair<ll,pll>
//#define mp make_pair
#define vv vector
#define endl '\n'

using namespace std;

// struct Cmp1{
// 	bool operator()(iii a,iii b){
// 		return a.ff > b.ff;
// 	}
// }

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;
	int arr[n];
	FOR(i,n)cin >> arr[i];

	int beforeLink[n];
	int afterLink[n];
	set<iii,greater<iii> > links;// greater
	FOR(i,n)afterLink[i] = beforeLink[i] = i;
	FOR(i,n)links.insert({arr[i],{i,i}});
	// set up has been done. 

	ll cost = 0;
	map<ii,ll> mp;
	FOR(i,n)mp[{i,i}] = arr[i];
	FOR(i,(n+1)/2){
		
		iii item = *(links.begin());
		cost += item.ff;
		links.erase(links.begin());
		// get the before item, and delete it;
		int st = item.ss.ff;
		int en = item.ss.ss;
		ll nc = -item.ff;
		if(item.ss.ff > 0){
			ll bcost = mp[{beforeLink[item.ss.ff-1],item.ss.ff-1}];
			links.erase({bcost,{beforeLink[item.ss.ff-1],item.ss.ff-1}});
		}
		if(item.ss.ss+1 < n){
			ll acost = mp[{item.ss.ss+1,afterLink[item.ss.ss+1]}];
			links.erase({acost,{item.ss.ss+1,afterLink[item.ss.ss+1]}});
		}
		if(item.ss.ff > 0 and item.ss.ss +1 <n){
			ll bcost = mp[{beforeLink[item.ss.ff-1],item.ss.ff-1}];
			ll acost = mp[{item.ss.ss+1,afterLink[item.ss.ss+1]}];
			nc += bcost + acost;
			
			afterLink[beforeLink[item.ss.ff-1]] = afterLink[item.ss.ss+1];
			beforeLink[afterLink[item.ss.ss+1]] = beforeLink[item.ss.ff-1];

			iii newitem = make_pair(nc,make_pair(beforeLink[item.ss.ff-1],afterLink[item.ss.ss+1]));
			//cout << "INSERTING: " << newitem.ff << " " << newitem.ss.ff << " " << newitem.ss.ss << endl;
			links.insert(newitem);
			mp[{beforeLink[item.ss.ff-1],afterLink[item.ss.ss+1]}] = nc;
		}
		cout << cost << endl;
	}


	return 0;
}

Compilation message

candies.cpp: In function 'int main()':
candies.cpp:67:7: warning: unused variable 'st' [-Wunused-variable]
   int st = item.ss.ff;
       ^~
candies.cpp:68:7: warning: unused variable 'en' [-Wunused-variable]
   int en = item.ss.ss;
       ^~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -