Game Rooms
Time Limit: 4000/4000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 305 Accepted Submission(s): 84
Luckily, you know who will work where in this building (everyone has picked out offices). You know that there will be Ti table tennis players and Pi pool players on each floor. Our goal is to minimize the sum of distances for each employee to their nearest game room. The distance is the difference in floor numbers: 0 if an employee is on the same floor as a game room of their desired type, 1 if the nearest game room of the desired type is exactly one floor above or below the employee, and so on.
2
10 5
4 3
In the first case, you can build a table tennis game room on the first floor and a pool game room on the second floor.
In this case, the 5 pool players on the first floor will need to go one floor up, and the 4 table tennis players on the second floor will need to go one floor down. So the total distance is 9.
#include <cstdio>
#include <iostream>
using namespace std; const int N = ;
typedef long long LL;
const LL MLL = 1000000000000000001LL;
int n, arr[N][];
LL distDown[N][], distUp[N][], sum[N][], dp[N][], ans; inline LL Up(int l, int r, bool s)
{
if(l > r) return ;
return (distUp[l][s ^ ] - distUp[r + ][s ^ ]) -
(sum[r][s ^ ] - sum[l - ][s ^ ]) * (n - r);
} inline LL Down(int l, int r, bool s)
{
if(l > r) return ;
return (distDown[r][s ^ ] - distDown[l - ][s ^ ]) -
(sum[r][s ^ ] - sum[l - ][s ^ ]) * (l - );
} inline LL Calc(int l, int r, bool state)
{
if(l == )
{
return Up(l, r, state);
}
int mid = (l + r) >> ;
return Up(mid + , r, state) + Down(l, mid, state);
} inline void Solve()
{
scanf("%d", &n);
for(int i = ; i <= n; i++)
for(int j = ; j < ; j++) scanf("%d", &arr[i][j]); for(int i = ; i < ; i++)
{
distDown[][i] = ;
for(int j = ; j <= n; j++)
{
distDown[j][i] = distDown[j - ][i] + 1LL * arr[j][i] * j;
sum[j][i] = sum[j - ][i] + arr[j][i];
}
distUp[n + ][i] = ;
for(int j = n; j >= ; j--)
distUp[j][i] = distUp[j + ][i] + 1LL * arr[j][i] * (n + - j);
} ans = MLL;
dp[][] = dp[][] = ;
for(int i = ; i < n; i++)
{
dp[i][] = dp[i][] = MLL;
for(int j = ; j < i; j++)
{
dp[i][] = min(dp[i][], dp[j][] + Calc(j + , i, ));
dp[i][] = min(dp[i][], dp[j][] + Calc(j + , i, ));
} ans = min(ans, dp[i][] + Down(i + , n, ));
ans = min(ans, dp[i][] + Down(i + , n, ));
}
cout << ans << endl;
} int main()
{
int test;
scanf("%d", &test);
for(int testnumber = ; testnumber <= test; testnumber++)
{
printf("Case #%d: ", testnumber);
Solve();
}
return ;
}