Editorial for Hai quân xe
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include <iostream> #include <algorithm> #include <cstdio> using namespace std; int n,a[333][333],row[333],col[333],ans; int main() { cin >> n; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) scanf("%d",a[i]+j), row[i]+=a[i][j], col[j]+=a[i][j]; for (int i=1;i<n;i++) for (int j=i+1;j<=n;j++) { int mxI=-(1<<29),mxJ=mxI; for (int k=1;k<=n;k++) { int vI=col[k]-a[i][k]*2-a[j][k]; int vJ=col[k]-a[i][k]-a[j][k]*2; ans=max(ans,row[i]+row[j]+mxI+vJ); ans=max(ans,row[i]+row[j]+mxJ+vI); ans=max(ans,row[i]+row[j]+col[k]-a[i][k]*2-a[j][k]*2); ans=max(ans,col[i]+col[j]+row[k]-a[k][i]*2-a[k][j]*2); mxJ=max(mxJ,vJ); mxI=max(mxI,vI); } } cout << ans << endl; }
Code mẫu của ladpro98
program c11rooks; uses math; const maxn=303; fi=''; var a:array[1..maxn,1..maxn] of longint; row,col,s1,s2:array[1..maxn] of longint; n,res:longint; procedure input; var inp:text; i,j:longint; begin assign(inp,fi); reset(inp); readln(inp,n); for i:=1 to n do begin for j:=1 to n do read(inp,a[i,j]); readln(inp); end; close(inp); end; procedure init; var i,j:longint; begin res:=low(longint); for i:=1 to n do begin row[i]:=0; for j:=1 to n do inc(row[i],a[i,j]); end; for j:=1 to n do begin col[j]:=0; for i:=1 to n do inc(col[j],a[i,j]); end; end; procedure process; var i,j,k,t,max1,max2:longint; begin for i:=1 to n do begin for k:=1 to n-1 do for j:=k+1 to n do res:=max(res,row[i]+col[k]+col[j]-2*a[i,k]-2*a[i,j]); for j:=i+1 to n do begin t:=row[i]+row[j]; for k:=1 to n do begin res:=max(res,t+col[k]-2*a[i,k]-2*a[j,k]); s1[k]:=col[k]-2*a[i,k]-a[j,k]; s2[k]:=col[k]-a[i,k]-2*a[j,k]; end; max1:=s1[1];max2:=s2[1]; for k:=2 to n do begin res:=max(res,t+s2[k]+max1); res:=max(res,t+s1[k]+max2); max1:=max(max1,s1[k]); max2:=max(max2,s2[k]); end; end; end; end; begin input; init; process; write(res); end.
Code mẫu của RR
#include <sstream> #include <iomanip> #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <map> #include <stack> #include <queue> #include <string> #include <deque> #include <complex> #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++) #define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--) #define SET(a,v) memset(a,v,sizeof(a)) #define sqr(x) ((x)*(x)) #define ll long long #define F first #define S second #define PB push_back #define MP make_pair #define DEBUG(x) cout << #x << " = "; cout << x << endl; #define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; #define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; using namespace std; //Buffer reading int INP,AM,REACHEOF; #define BUFSIZE (1<<12) char BUF[BUFSIZE+1], *inp=BUF; #define GETCHAR(INP) { \ if(!*inp) { \ if (REACHEOF) return 0;\ memset(BUF,0,sizeof BUF);\ int inpzzz = fread(BUF,1,BUFSIZE,stdin);\ if (inpzzz != BUFSIZE) REACHEOF = true;\ inp=BUF; \ } \ INP=*inp++; \ } #define DIG(a) (((a)>='0')&&((a)<='9')) #define GN(j) { \ AM=0;\ GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\ if (INP=='-') {AM=1;GETCHAR(INP);} \ j=INP-'0'; GETCHAR(INP); \ while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \ if (AM) j=-j;\ } //End of buffer reading const long double PI = acos((long double) -1.0); const int MN = 333; int n, a[MN][MN]; int row[MN], col[MN], best[2][MN][MN], save[2][MN][MN], cc[MN][MN], rr[MN][MN]; int main() { while (scanf("%d", &n) == 1) { memset(row, 0, sizeof row); memset(col, 0, sizeof col); FOR(i,1,n) FOR(j,1,n) { scanf("%d", &a[i][j]); row[i] += a[i][j]; col[j] += a[i][j]; } FOR(i,1,n) FOR(j,1,n) { cc[i][j] = col[i] + col[j]; rr[i][j] = row[i] + row[j]; } int res = 0; // Same row FOR(i,1,n) { FOR(j1,1,n) FOR(j2,j1+1,n) { res = max(res, cc[j1][j2] + row[i] - 2*(a[i][j1] + a[i][j2])); } } // Same column FOR(j,1,n) { FOR(i1,1,n) FOR(i2,i1+1,n) { res = max(res, rr[i1][i2] + col[j] - 2*(a[i1][j] + a[i2][j])); } } // Different row, different column int now; FOR(i1,1,n) FOR(i2,1,n) if (i1 != i2) { best[0][i1][i2] = best[1][i1][i2] - 1000111000; int t = rr[i1][i2]; FOR(j,1,n) { now = col[j] - 2*a[i2][j] - a[i1][j] + t; if (now > best[0][i1][i2]) { best[0][i1][i2] = now; save[0][i1][i2] = j; } else if (now > best[1][i1][i2]) { best[1][i1][i2] = now; save[1][i1][i2] = j; } } } FOR(i1,1,n) FOR(i2,1,n) if (i1 != i2) FOR(j1,1,n) { if (j1 == save[0][i1][i2]) res = max(res, col[j1] - 2*a[i1][j1] - a[i2][j1] + best[1][i1][i2]); else res = max(res, col[j1] - 2*a[i1][j1] - a[i2][j1] + best[0][i1][i2]); } cout << res << endl; } return 0; }
Code mẫu của hieult
#include <set> #include <map> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <sstream> #include <iomanip> #include <iostream> #include <algorithm> #include <ctime> #include <deque> #include <bitset> #include <cctype> #include <utility> #include <cassert> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned int ui; typedef unsigned long long ull; #define Rep(i,n) for(int i = 0; i < (n); ++i) #define Repd(i,n) for(int i = (n)-1; i >= 0; --i) #define For(i,a,b) for(int i = (a); i <= (b); ++i) #define Ford(i,a,b) for(int i = (a); i >= (b); --i) #define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i) #define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i) #define mp make_pair #define pb push_back #define fi first #define se second #define sz(a) ((int)(a).size()) #define all(a) (a).begin(), (a).end() #define ms(a,x) memset(a, x, sizeof(a)) template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; } template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; } template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } template<class T> T sqr(T x) { return x * x; } template<class T> T cube(T x) { return x * x * x; } template<class T> int getbit(T s, int i) { return (s >> i) & 1; } template<class T> T onbit(T s, int i) { return s | (T(1) << i); } template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); } template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); } typedef pair<int, int> II; const double PI = acos(-1.0); const double eps = 1e-3; const int dr[] = { -1, 0, +1, 0 }; const int dc[] = { 0, +1, 0, -1 }; const int inf = (int) 1e9 + 5; const ll linf = (ll) 1e16 + 5; const ll mod = (ll) 1e9 + 7; #define maxn 305 int n, a[maxn][maxn], sumr[maxn], sumc[maxn], A[maxn], B[maxn]; int cal(int c[],int d[]){ int vt = -1, MAX = -1, res = 0; For(i, 1, n) if(c[i] > MAX){ MAX = c[i]; vt = i; } res = MAX; MAX = -1; For(i, 1, n) if(d[i] > MAX && i != vt){ MAX = d[i]; } res += MAX; return res; } int main() { // freopen("in.txt", "r", stdin); ms(sumr, 0); ms(sumc, 0); cin >> n; For(i, 1, n) For(j, 1, n){ scanf("%d", &a[i][j]); sumr[i] += a[i][j]; sumc[j] += a[i][j]; } int res = 0; For(i, 1, n) For(j, i + 1, n){ int ret = 0; ret += sumr[i] + sumr[j]; for(int k = 1; k <= n; k++){ A[k] = sumc[k] - a[i][k] - 2 * a[j][k]; B[k] = sumc[k] - 2 * a[i][k] - a[j][k]; } ret += max(cal(A, B), cal(B, A)); res = max(res, ret); } For(i, 1, n){ int ret = sumr[i]; for(int k = 1; k <= n; k++){ A[k] = sumc[k] - 2 * a[i][k]; } ret += cal(A, A); res = max(res, ret); } For(i, 1, n){ int ret = sumc[i]; for(int k = 1; k <= n; k++){ A[k] = sumr[k] - 2 * a[k][i]; } ret += cal(A, A); res = max(res, ret); } cout << res; // cout << clock() << endl; return 0; }
Code mẫu của skyvn97
#include<stdio.h> #define MAX 350 int a[MAX][MAX]; int r[MAX]; int c[MAX]; int n,b; void init(void) { int i,j; scanf("%d",&n); for (i=1;i<=n;i=i+1) for (j=1;j<=n;j=j+1) { scanf("%d",&a[i][j]); r[i]+=a[i][j]; c[j]+=a[i][j]; } } int max(int x,int y) { int i,cx,cy,mx,my; mx=-32000; my=-32000; for (i=1;i<=n;i=i+1) if (c[i]-2*a[x][i]-a[y][i]>mx) { mx=c[i]-2*a[x][i]-a[y][i]; cx=i; } for (i=1;i<=n;i=i+1) if (c[i]-2*a[y][i]-a[x][i]>my) { my=c[i]-2*a[y][i]-a[x][i]; cy=i; } if (cx!=cy) return (mx+my+r[x]+r[y]); int cx1,cy1,mx1,my1; mx1=-32000; my1=-32000; for (i=1;i<=n;i=i+1) if ((i!=cx) && (c[i]-2*a[x][i]-a[y][i]>mx1)) { mx1=c[i]-2*a[x][i]-a[y][i]; cx1=i; } for (i=1;i<=n;i=i+1) if ((i!=cy) && (c[i]-2*a[y][i]-a[x][i]>my1)) { my1=c[i]-2*a[y][i]-a[x][i]; cy1=i; } if (mx1+my>my1+mx) return (mx1+my+r[x]+r[y]); return (my1+mx+r[x]+r[y]); } void process(void) { b=-32000; int i,j,k; for (i=1;i<n;i=i+1) for (j=i+1;j<=n;j=j+1) { k=max(i,j); if (k>b) b=k; } for (i=1;i<=n;i=i+1) for (j=1;j<n;j=j+1) for (k=j+1;k<=n;k=k+1) { if (r[i]+c[j]+c[k]-2*a[i][j]-2*a[i][k]>b) b=r[i]+c[j]+c[k]-2*a[i][j]-2*a[i][k]; if (c[i]+r[j]+r[k]-2*a[j][i]-2*a[k][i]>b) b=c[i]+r[j]+r[k]-2*a[j][i]-2*a[k][i]; } printf("%d",b); } int main(void) { init(); process(); }
Comments