链接：https://www.nowcoder.com/acm/contest/212/C 来源：牛客网
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<vector> #include<queue> #include<set> #define mem(a,x) memset(a,x,sizeof(a)) #define s1(x) scanf("%d",&x) #define s2(x,y) scanf("%d%d",&x,&y) #define s3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define s4(x,y,z,k) scanf("%d%d%d%d",&x,&y,&z,&k) #define ls 2*rt #define rs 2*rt+1 #define lson ls,L,mid #define rson rs,mid+1,R #define ll long long using namespace std; typedef pair<int,int> pii; //inline ll ask(int x){ll res=0;while(x)res+=c[x],x-=x&(-x);return res;} //inline void add(int x,int d){while(x<=n)c[x]+=d,x+=x&(-x);} //int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b);} const ll inf = 0x3f3f3f3f; const int mx = 1e5+10; struct no{ int l,r,c,len; }p[mx]; vector<int> ve[mx*2]; int n,m,co; int ran[mx*2]; ll dp[mx*2][(1<<7)+0]; //两倍 bool cmp(no &a, no &b){ return a.r < b.r; } int find(int x){ return lower_bound(ran+1,ran+1+co,x)-ran; //莫名其妙减一 } int count(int x){ int ans = 0; for(int i = 0; i <= 6; i++){ if(x&(1<<i)) // ans++; } return ans; } int main(){ // freopen("F:\\in.txt","r",stdin); //int T=10; scanf("%d",&T); s2(n,m); co = 0; for(int i = 1; i <= n; i++){ s3(p[i].l,p[i].r,p[i].c); p[i].c--; p[i].len = p[i].r-p[i].l; //不加一 ran[++co] =p[i].l; ran[++co] = p[i].r; } sort(ran+1,ran+1+co); //忘了这句 co = unique(ran+1,ran+1+co)-ran-1; int id,ob,l,r,col,pre; sort(p+1,p+1+n,cmp); // 这个也要排序 for(int i = 1; i <= n ; i++){ id = find(p[i].r); ve[id].push_back(i); } for(int i = 1; i <= co; i++){ for(int j = 0; j < (1<<7); j++){ dp[i][j] = max(dp[i][j],dp[i-1][j]); for(int k = 0; k < ve[i].size(); k++){ ob = ve[i][k]; pre = find(p[ob].l)-1; col = j|(1<<p[ob].c); if(dp[pre][j]==0 && j)//等于0没写 continue; dp[i][col]=max(dp[i][col],dp[pre][j]+p[ob].len); } } } ll ans = 0; for(int i = 1; i <(1<<7); i++){ if(count(i) == m){ ans = max(ans,dp[co][i]); } } // cout<<"yes"<<endl; printf("%lld\n",ans > 0 ? ans:-1); return 0; }
