Main » 2013 October 9 » 「Poetize10」封印一击
2:55 PM 「Poetize10」封印一击 |
水题#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<vector> #include<set> #include<map> #include<string> #include<algorithm> #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) #define pb push_back #define mp make_pair #define N 500010 using namespace std; typedef long long LL; typedef long double LD; struct node{LL d;int type;}; int cmp(node a,node b) { if (a.d<b.d) return 1; if (a.d>b.d) return 0; return a.type>b.type; } node b[N]; int n,i,len; LL tot=0,L,R; int main() { ios::sync_with_stdio(false); cin>>n; int len=0; FOR(i,1,n) { cin>>L>>R; len++; tot+=L; b[len].type=0;b[len].d=L; len++; b[len].type=1;b[len].d=R; } sort(b+1,b+1+len,cmp); int pos;LL tmp=0,ans=0; FOR(i,1,len) { if (b[i].type==0) { tmp++;tot-=b[i].d; if (tot+b[i].d*tmp>ans) {ans=tot+b[i].d*tmp;pos=b[i].d;} }else { if (tot+b[i].d*tmp>ans) {ans=tot+b[i].d*tmp;pos=b[i].d;} tmp--; } } cout<<pos<<' '<<ans<<endl; return 0; } |
|
|
| Total comments: 0 | |