#include <iostream> #include <cstdlib> #include <cstdio> #define SZ 10005 #define INF 100000000 #define ll long long using namespace std; ll a[SZ]; int main() { ll N,M,MN; bool f=0; ll price2,price1; price2 = 1000001; price1 = 1000001; int d = price1+price2; //cout<<d<<"\n"; while(cin>>N) { MN = INF; for(int i=0;i<N;i++) cin>>a[i]; cin>>M; for(int i=0;i<N;i++) { for(int j=0;j<N;j++)
Category: Algorithm
10667
#include <iostream> using namespace std; int arr[105][105]; int s; int Matsum(int a,int b) { int p; int Line[105]; int max_end_here,max_so_far; for(int i=1;i<=s;i++) { p=0; for(int j=a;j<=b;j++) { p+=arr[j][i]; } Line[i]=p; } max_end_here=0; max_so_far=0; for(int i=1;i<=s;i++) { max_end_here+=Line[i]; if(max_end_here<0) max_end_here=0; if(max_end_here>max_so_far) max_so_far=max_end_here; } return max_so_far; } int main() { int t,mx,m; int b,r1,r2,c1,c2; cin>>t; while(t–) {
10074
#include <iostream> using namespace std; int arr[105][105]; int M,N; int Matsum(int a,int b) { int p,max_end_here=0,max_so_far=0; int Line[105]; for(int i=1;i<=N;i++) { p = 0; for(int j=a;j<=b;j++) { p+=arr[j][i]; } Line[i]=p; } max_end_here=0; max_so_far=0; for(int i=1;i<=N;i++) { max_end_here = max_end_here + Line[i]; if(max_end_here<0) max_end_here = 0; if(max_so_far<max_end_here) max_so_far = max_end_here; } return max_so_far; } int main()
108
#include <stdio.h> int a[100][100]={0}; int N; int Line[100]; int KadaneAlg(); int MatSum(int a,int b); int main() { int p=-100; int Max=-100; while(scanf("%d",&N)==1) { Max=-100; p =-100; for(int i=0;i<N;i++) { for(int j=0;j<N;j++) scanf("%d",&a[i][j]); } for(int k=0;k<N;k++) { for(int l=k;l<N;l++) { p = MatSum(k,l); if(p>Max) Max = p; } } printf("%d\n",Max); } return 0; } int MatSum(int
836
This problem also can be solved using Dynamic Programming. #include <iostream> #include <string> #include <cstring> #include <cstdio> using namespace std; string *str = new string [50]; int N; int kaadanealgo(int a,int b) { int line[50]; int max_end_here=0; int max_so_far=0; for(int i=0;i<N;i++) { line[i] = 0; for(int j=a;j<=b;j++) { if(str[j][i]=='0') line[i]+=-1000000; else line[i]+=(str[j][i]-'0'); } } for(int
558
#include <iostream> #include <cstdio> #include <cstdlib> #define INF 1000000000 #define MX 2005 using namespace std; struct Edge{ int src; int dst; int weight; }; Edge e[MX]; bool bellman(int n,int m,int source) { bool negativecycle =false; int dist[n+5]; dist = 0; for(int i=1;i<n;i++) dist[i]=INF; for(int i=1;i<=n-1;i++) { for(int j=0;j<m;j++) { if(dist[e[j].dst]>dist[e[j].src]+e[j].weight) dist[e[j].dst] = dist[e[j].src]+e[j].weight; } }
273
Line Segment Intersection: 1. General Case: a) (p1, q1, p2) and (p1, q1, q2) have different orientations and b) (p2, q2, p1) and (p2, q2, q1) have different orientations 2. Special Case a) (p1, q1, p2), (p1, q1, q2), (p2, q2, p1), and (p2, q2, q1) are all collinear and b) the x-projections of (p1,
924
#include <iostream> #include <string.h> #include <vector> #include <queue> #define ll long long #define INF 10000000 using namespace std; vector<int> vb; vector<int> gr[2501]; int s,n; int daymap[2501]; void bfs(int src) { int day[2501]; bool visit[2501]; for(int i=0;i<2501;i++) { daymap[i]=-1; day[i]=-1; visit[i]=false; } visit[src]=1; day[0]+=1; daymap[src]=0; queue<int> q; q.push(src); int a; while(!q.empty()) { a = q.front(); q.pop();
10044
#include <iostream> #include <string.h> #include <string> #include <vector> #include <cstdio> #include <map> #define ll long long #define MAX_WORD 105 #define INF 100000000 using namespace std; int min_arr[1000001]; map<string,int> nameErdos; int minval(string **vb,int i) { int v = nameErdos[0]]; for(int j=1;vb[i][j]!="END";j++) { v = min(v,nameErdos[j]]); } return v; } int main() { int t,P,N,MN; int kase=1;
10910
Top Down: #include <iostream> #include <cstdio> #include <vector> #include <cstdlib> #define INF 1000 #define ll long long using namespace std; ll res[75][75]; int N,T,P; ll dp(int cnt,int rem) { if(cnt==1 || rem==0) return 1; if(res[cnt][rem]!=-1) return res[cnt][rem]; ll r =0; for(int i=0;i<=rem;i++) { r+= dp(cnt-1,rem-i); } res[cnt][rem]=r; return res[cnt][rem]; } int main() { int t;