Guest User

Untitled

a guest
Nov 10th, 2017
309
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.11 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define pii pair<int,int>
  5. #define pll pair<ll,ll>
  6. #define pdd pair<double,double>
  7. #define X first
  8. #define Y second
  9. #define REP(i,a) for(int i=0;i<a;++i)
  10. #define REPP(i,a,b) for(int i=a;i<b;++i)
  11. #define FILL(a,x) memset(a,x,sizeof(a))
  12. #define foreach( gg,itit )  for( typeof(gg.begin()) itit=gg.begin();itit!=gg.end();itit++ )
  13. #define mp make_pair
  14. #define pb push_back
  15.  
  16. inline int max(int a,int b){return a<b?b:a;}
  17. inline int min(int a,int b){return a>b?b:a;}
  18. inline ll max(ll a,ll b){return a<b?b:a;}
  19. inline ll min(ll a,ll b){return a>b?b:a;}
  20. const int mod = 1e9+7;
  21. const int N = 1e6+10;
  22. const ll INF = 1e18;
  23.  
  24. int dp[405][405];
  25. int main(){
  26.   int n,q;
  27.   FILL(dp,0);
  28.   scanf("%d%d",&n,&q);
  29.   int ans=mod;
  30.   REP(i,q){
  31.     int x,y;
  32.     scanf("%d%d",&x,&y);x--;y--;
  33.     dp[x][y]++;
  34.   }
  35.   REP(i,n){
  36.     int x=0;
  37.     REP(j,n) if(j>=i) x+=dp[i][j];
  38.     ans=min(ans,x);
  39.     if(x==0) break;
  40.     REP(j,n) if(dp[i][j]>0) { x=j;}
  41.     REP(j,n) if(j<x&&dp[i][j]>0){
  42.       dp[j+1][x]+=dp[i][j];
  43.     }
  44.   }
  45.   printf("%d\n",ans);
  46.   return 0;
  47. }
Add Comment
Please, Sign In to add comment