oj.uz

Submission #48255

# Submission time Handle Problem Language Result Execution time Memory
48255 2018-05-11T06:31:01 Z WA_TLE Palembang Bridges (APIO15_bridge) C++14
100 / 100
 181 ms 5764 KB 
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<bitset>
#include<iomanip>
#include<list>
#include <numeric>
using namespace std;
typedef unsigned long long int ulint;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define RE return 0
//ios::sync_with_stdio(false);
//std::cin.tie(0);
//<< setprecision(20)
const int mod=(int)1e9+7;
const llint big=(llint)(2.19e15+1);
const long double pai=3.141592653589793238462643383279502884197;
const long double ena=2.71828182845904523536;
const long double eps=1e-7;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
template <class T> void soun(T& ar)
{sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());}
llint gcd(llint a,llint b){if(a%b==0){return b;}else{return gcd(b,a%b);}}
llint lcm(llint a,llint b){return a/gcd(a,b) *b;}
template<class T,class U> auto LB(T& ve,U in){return lower_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto UB(T& ve,U in){return upper_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto LBI(T& ve,U in){return LB(ve,in)-ve.begin();}
template<class T,class U> auto UBI(T& ve,U in){return UB(ve,in)-ve.begin();}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
int main(void){
	int K,n,i;cin>>K>>n;
	llint mto=0;
	vector<tuple<llint,llint,llint>>ie;
	ie.reserve(n);
	for(i=0;i<n;i++){
		char ca,cb;llint ba,bb;
		cin>>ca>>ba>>cb>>bb;
		if(ba>bb){swap(ba,bb);}
		if(ca!=cb){mto++;ie.pub(mt(ba+bb,ba,bb));}
		else{mto+=bb-ba;}
	}
	SO(ie);
	n=ie.size();
	if(n==0){cout<<mto<<endl;return 0;}
	vector<llint>haL(n+1);
	vector<llint>haR(n+1);
	llint gen=0;
	priority_queue<llint>que;//でかいのを出力に注意
	for(i=0;i<n;i++){
		que.push(-get<1>(ie[i]));gen+=get<1>(ie[i]);
		que.push(-get<2>(ie[i]));gen+=get<2>(ie[i]);
		gen+=2*que.top();que.pop();
		haL[i+1]=gen;
	}
		while(que.size()>0){que.pop();}
	gen=0;
	for(i=1;i<=n;i++){
		que.push(get<1>(ie[n-i]));gen-=get<1>(ie[n-i]);
		que.push(get<2>(ie[n-i]));gen-=get<2>(ie[n-i]);
		gen+=2*que.top();que.pop();
		haR[i]=gen;
	}
	llint ans=big;
	if(K==2){for(i=0;i<=n;i++){mineq(ans,haL[i]+haR[n-i]);}}
	else{ans=haL[n];}
	cout<<ans+mto<<endl;
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 428 KB Output is correct
4 Correct 3 ms 480 KB Output is correct
5 Correct 5 ms 480 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 5 ms 724 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 3 ms 724 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 4 ms 724 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 4 ms 724 KB Output is correct
12 Correct 106 ms 5608 KB Output is correct
13 Correct 181 ms 5700 KB Output is correct
14 Correct 134 ms 5700 KB Output is correct
15 Correct 101 ms 5700 KB Output is correct
16 Correct 117 ms 5700 KB Output is correct
17 Correct 152 ms 5700 KB Output is correct
18 Correct 140 ms 5700 KB Output is correct
19 Correct 180 ms 5700 KB Output is correct
20 Correct 156 ms 5700 KB Output is correct
21 Correct 148 ms 5700 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5700 KB Output is correct
2 Correct 2 ms 5700 KB Output is correct
3 Correct 2 ms 5700 KB Output is correct
4 Correct 2 ms 5700 KB Output is correct
5 Correct 2 ms 5700 KB Output is correct
6 Correct 2 ms 5700 KB Output is correct
7 Correct 2 ms 5700 KB Output is correct
8 Correct 2 ms 5700 KB Output is correct
9 Correct 2 ms 5700 KB Output is correct
10 Correct 2 ms 5700 KB Output is correct
11 Correct 2 ms 5700 KB Output is correct
12 Correct 2 ms 5700 KB Output is correct
13 Correct 3 ms 5700 KB Output is correct
14 Correct 3 ms 5700 KB Output is correct
15 Correct 3 ms 5700 KB Output is correct
16 Correct 2 ms 5700 KB Output is correct
17 Correct 2 ms 5700 KB Output is correct
18 Correct 2 ms 5700 KB Output is correct
19 Correct 3 ms 5700 KB Output is correct
20 Correct 3 ms 5700 KB Output is correct
21 Correct 3 ms 5700 KB Output is correct
22 Correct 3 ms 5700 KB Output is correct
23 Correct 3 ms 5700 KB Output is correct
24 Correct 3 ms 5700 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5700 KB Output is correct
2 Correct 2 ms 5700 KB Output is correct
3 Correct 2 ms 5700 KB Output is correct
4 Correct 2 ms 5700 KB Output is correct
5 Correct 2 ms 5700 KB Output is correct
6 Correct 2 ms 5700 KB Output is correct
7 Correct 2 ms 5700 KB Output is correct
8 Correct 2 ms 5700 KB Output is correct
9 Correct 2 ms 5700 KB Output is correct
10 Correct 2 ms 5700 KB Output is correct
11 Correct 2 ms 5700 KB Output is correct
12 Correct 2 ms 5700 KB Output is correct
13 Correct 3 ms 5700 KB Output is correct
14 Correct 3 ms 5700 KB Output is correct
15 Correct 3 ms 5700 KB Output is correct
16 Correct 2 ms 5700 KB Output is correct
17 Correct 2 ms 5700 KB Output is correct
18 Correct 2 ms 5700 KB Output is correct
19 Correct 3 ms 5700 KB Output is correct
20 Correct 3 ms 5700 KB Output is correct
21 Correct 3 ms 5700 KB Output is correct
22 Correct 4 ms 5700 KB Output is correct
23 Correct 4 ms 5700 KB Output is correct
24 Correct 3 ms 5700 KB Output is correct
25 Correct 89 ms 5700 KB Output is correct
26 Correct 110 ms 5700 KB Output is correct
27 Correct 154 ms 5700 KB Output is correct
28 Correct 179 ms 5704 KB Output is correct
29 Correct 174 ms 5704 KB Output is correct
30 Correct 94 ms 5704 KB Output is correct
31 Correct 117 ms 5704 KB Output is correct
32 Correct 154 ms 5704 KB Output is correct
33 Correct 143 ms 5748 KB Output is correct
34 Correct 167 ms 5764 KB Output is correct
35 Correct 126 ms 5764 KB Output is correct
36 Correct 150 ms 5764 KB Output is correct
37 Correct 75 ms 5764 KB Output is correct