ACM-ICPC Live Archive Regionals 2014 >> Asia - Shanghai

Show All Problems

Problems Soluble
J - World Cup
I - Defeat the Enemy
B - Rotation

---

It is merely a problem about induction and deduction that trouble us mostly... The (m+1)th team has to be considered specially.

/**
 * Dec 1, 2015 8:20:12 PM
 * PrjName: LA7147
 * @semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException{
		InputReader in=new InputReader(System.in);
		PrintWriter out=new PrintWriter(System.out);
		int T=in.nextInt(),cas=0;
		while(T-->0){
			long n=in.nextLong();
			long m=in.nextLong();
			long a=in.nextLong();
			long b=in.nextLong();
			long c=in.nextLong();
			if (a<c){
				a^=c;c^=a;a^=c;
			}
			long ans1=Math.max(a, b)*(n-m-1);
			long ans2=Math.min(c, b)*(m-1);
			ans1+=Math.max(b*m, m/2*a+m/2*c+((m&1L)>0?Math.max(b, c):0));
			ans2+=Math.min(b*(n-m), (n-m)/2*a+(n-m)/2*c+((n-m&1L)>0?Math.min(b, a):0));
			out.println("Case #"+(++cas)+": "+ans1+" "+ans2);
		}
		out.flush();
		out.close();
	}

---

Bipartite graph matching turns out to exceed the time limit.Use greedy strategy as estimated. Reflecting back upon the on-site period,the sort comparator can be considered correct.But the improper linear data structure failed to perform a "delete" operation. Now use `multiset` instead. Note that the optimal result doesn't necessarily have to do with that earlier or later one of the tribes battles. [code language="cpp"] /* * File: main.cpp * Author: semprathlon * * Created on December 2, 2015, 7:31 PM */

#include
#include
#include
#include
#include

using namespace std;

typedef pair<int,int> pr;
const int maxn=100010;

multiset st;

pr c[maxn],e[maxn];

bool cmp1(const pr &a,const pr &b){
return a.first>b.first;
}

bool cmp2(const pr &a,const pr &b){
return a.second>b.second;
}

int main() {
int T,cas=0;
scanf(“%d”,&T);
while(T–){
int n,m;
scanf(“%d%d”,&n,&m);
for(int i=0;i<n;i++){
int a,d;
scanf(“%d%d”,&a,&d);
c[i]=std::make_pair(a,d);
}
for(int i=0;i<m;i++){
int a,d;
scanf(“%d%d”,&a,&d);
e[i]=std::make_pair(a,d);
}
std::sort(c,c+n,cmp1);
std::sort(e,e+m,cmp2);
// for(int i=0;i<n;i++) printf(“%d,%d\n”,c[i].first,c[i].second);
// for(int i=0;i<m;i++) printf(“%d,%d\n”,e[i].first,e[i].second);
int ans=n;
st.clear();
for(int i=0,j=0;i<m;i++){
for(;j<n&&c[j].first>=e[i].second;j++)
st.insert(c[j].second);
if (st.empty()){
ans=-1;break;
}
multiset::iterator it=st.upper_bound(e[i].first);
if (it==st.end()){
st.erase(st.begin());
ans–;
}
else
st.erase(it);
}
printf(“Case #%d: %d\n”,++cas,ans);
}
return 0;
}

------

<iframe src="https://icpcarchive.ecs.baylor.edu/external/71/7139.pdf" width="100%" height="600" scrolling="auto" frameborder="0"></iframe>
Terrific mistake occurred when reading the description of the problem.The path only add some value to the grids `adjacent` to it.
Also,pay attention to the `square sum`.
```java
/**
 * Dec 4, 2015 9:03:20 PM
 * PrjName: LA7139
 * @semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
	static int[][] g;
	static void add(int r,int c1,int c2,int v){
		g[r][c1]+=v;
		g[r][c2]-=v;
	}
	static void debug(int n,int m,PrintWriter out){
		for(int i=1;i<=n+1;i++){
			for(int j=1;j<=m+1;j++)
				out.print(g[i][j]+" ");
			out.println();
		}
	}
	public static void main(String[] args) throws IOException{
		InputReader in=new InputReader(System.in);
		PrintWriter out=new PrintWriter(System.out);
		int T=in.nextInt(),cas=0;
		while(T-->0){
			int n=in.nextInt();
			int m=in.nextInt();
			int k=in.nextInt();
			g=new int[n+2][m+2];
			int x=1,y=1; 
			for(int i=1;i<=k;i++){
				String s=in.next();
				int l=in.nextInt();
				switch (s.charAt(0)) {
				case 'R':
					add(x,y,y+l,1);y+=l;break;
				case 'L':
					add(x, y-l, y, -1);y-=l;break;
				case 'U':
					x-=l;break;
				case 'D':
					x+=l;break;
				}
			}

			long ans=0;
			for(int i=1;i<=n;i++)
				for(int j=1;j<=m;j++){
					g[i][j]+=g[i][j-1];
					g[i][j]+=g[i-1][j];
					g[i][j]-=g[i-1][j-1];
					ans+=g[i][j]*g[i][j];
					
				}
//			debug(n, m, out);
			out.println("Case #"+(++cas)+": "+ans);
		}
		out.flush();
		out.close();
	}

}