제출 #598345

#제출 시각아이디문제언어결과실행 시간메모리
598345Koosha_mvArranging Tickets (JOI17_arranging_tickets)C++14
0 / 100
1 ms340 KiB
#include <bits/stdc++.h> using namespace std; #define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl #define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl #define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl #define eror(x) cout<<#x<<'='<<(x)<<endl #define f_(i,a,b) for(int i=a;i>=b;i--) #define f(i,a,b) for(int i=a;i<b;i++) #define nb(x) __builtin_popcount(x) #define all(v) v.begin(),v.end() #define bit(n,k) (((n)>>(k))&1) #define Add(x,y) x=(x+y)%mod #define maxm(a,b) a=max(a,b) #define minm(a,b) a=min(a,b) #define lst(x) x[x.size()-1] #define sz(x) int(x.size()) #define mp make_pair #define ll long long #define pb push_back #define S second #define F first const int N=3030; int n,m,ans,cnt,a[N],b[N],s[N],t[N],ok[N]; vector<int> v[N]; void solve(int x){ int sum=0,cnt=0; set<pair<int,int> > s; f(i,0,n) b[i]=0; f(i,0,n){ sum+=a[i]+b[i]; f(j,0,v[i].size()){ s.insert(mp(v[i][j],cnt++)); } while(sum<x){ if(s.size()==0) return ; int x=(*s.rbegin()).F; s.erase(*s.rbegin()); b[x]-=2; sum+=2; } } cout<<x<<" -> "<<sz(s)<<endl; maxm(ans,x+sz(s)); } void do_it(){ pair<int,int> mn=mp(N,0); f(i,0,m){ if(ok[i]) continue ; int mx=-N; f(j,s[i],t[i]) maxm(mx,a[j]); minm(mn,mp(mx,i)); } int id=mn.S; ok[id]=1; f(i,s[id],t[id]) a[i]+=2; cnt--; } int calc(){ int mx=-m; f(i,0,n) maxm(mx,a[i]); return mx+cnt; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m; ans=cnt=m; f(i,0,m){ int c; cin>>s[i]>>t[i]>>c; if(s[i]>t[i]) swap(s[i],t[i]); s[i]--; t[i]--; a[s[i]]--; a[t[i]]++; v[s[i]].pb(t[i]); } f(i,0,n) a[i+1]+=a[i]; f(i,0,m){ minm(ans,calc()); //eror(calc()); do_it(); } minm(ans,calc()); cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...