fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int Long;
  4. //typedef long long int ll;
  5. typedef int ll;
  6. typedef ll ft;
  7. typedef set<int> si;
  8. typedef long long Long;
  9. typedef vector<int> vi;
  10. typedef vector<vi> vii;
  11. typedef vector<Long>vl;
  12. typedef pair<int,int>pii;
  13. typedef pair<Long,Long>pll;
  14. typedef pair<string,int>psi;
  15. typedef pair<double,double>pdd;
  16. #define get getchar_unlocked
  17. #define put putchar_unlocked
  18. #define pb push_back
  19. #define mp make_pair
  20. #define ff first
  21. #define ss second
  22. #define sz size()
  23. #define ln length()
  24. #define repstl(i, s) for (__typeof((s).end())i=(s).begin();i!=(s).end();++i)
  25. #define debug1(s,a) cout << s << " " << a << " " << endl;
  26. #define debug2(s,a,b) cout << s << " " << a << " " << b << " " << endl
  27. #define debug3(s,a,b,c) cout << s << " " << a << " " << b << " " << c << " " << endl;
  28. #define debug4(s,a,b,c,d) cout << s << " " << a << " " << b << " " << c << " " << d << " " << endl;
  29. #define debug5(s,a,b,c,d,e) cout << s << " " << a << " " << b << " " << c << " " << d << " " << e << " " << endl;
  30. #define PI 3.1415926535897932384626433832795
  31. #define FO freopen ("out.txt", "w", stdout)
  32. #define FI freopen ("in.txt", "r", stdin)
  33. #define ref(i,a,n) for(int i=a;i<=n;i++)
  34. #define reb(i,n,a) for(int i=n;i>=a;i--)
  35. #define rep(i,n) for(int i=0;i<n;i++)
  36. #define all(a) a.begin(),a.end()
  37. #define gi(n) scanf("%d",&n)
  38. #define gii(n) scanf("%lld",&n)
  39. #define gc(c) scanf(" %c",&c)
  40. #define gs(s) scanf(" %s",s);
  41. #define pi(n) printf("%d",n)
  42. #define pii(n) printf("%lld",n)
  43. #define pc(c) printf("%c",c)
  44. #define ps printf(" ")
  45. #define pn printf("\n")
  46. #define pl(a) printf("%s",a)
  47. #define l(a) 2*a+1
  48. #define r(a) 2*a+2
  49. #define left(a,b) a,(a+b)/2
  50. #define right(a,b) (a+b)/2+1,b
  51. #define mid(a,b) (a+b)/2
  52. void gl(char *str){register char c=0;register int i=0;while(c<33)c=get();while(c!='\n'){str[i]=c;c=get();i=i+1;}str[i]='\0';}
  53. void gfi(ft &x) {register ft c = get(); x = 0; ft sn=1;for(;(c<48 || c>57);c = get()) if(c=='-') sn=-1;for(;c>47 && c<58;c = get()) {x = (x<<1) + (x<<3) + c - 48;}x*=sn;}
  54. //int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
  55. //int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
  56. //int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
  57. //int dx[]={2,1,-1,-2,-1,1};int dy[]={0,1,1,0,-1,-1}; //Hexagonal Direction
  58.  
  59. #define MAX 2000000009
  60. #define N 10005
  61. ll n,cap[N],ass[N],dp[N][N];
  62.  
  63. ll solve(ll ind,ll more) {
  64. 	if(ind==n && more==0) return 0;
  65. 	if(ind==n) return MAX; 
  66. 	if(dp[ind][more]!=-1) return dp[ind][more];
  67. 	if(more>0) return dp[ind][more]=min(ass[ind]+solve(ind+1,more-1),cap[ind]+solve(ind+1,more+1));
  68. 	else return dp[ind][more]=cap[ind]+solve(ind+1,more+1);
  69. }
  70.  
  71. int main() {
  72. 	gfi(n);
  73. 	rep(i,n) gfi(ass[i]),gfi(cap[i]);
  74. 	rep(i,n) rep(j,n) dp[i][j]=-1;
  75. 	pi(cap[0]+solve(1,1));pn;
  76. 	return 0;
  77. }
  78.  
Time limit exceeded #stdin #stdout 5s 394240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/58WHSN
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!