当前位置:网站首页>Codeforces Global Round 19
Codeforces Global Round 19
2022-07-07 07:46:00 【whitewall_ nine】
B.
This competition is full of violence , I didn't expect the positive solution , For such a complex situation, there must be a conclusion that can make the topic simple . Yes A Speaking of, if it has been ordered , Then it must be no otherwise It indicates that there is a point a[i] > a[j], i < j Or let a[i] < a[j] i > j For the first case, it must be YES, For the second case, we can let j - 1 It is also natural and non reducing . Explain that if there is no order , It must be YES about B Consider greed , Because we need to make the value as big as possible , Let's divide into as many paragraphs as possible , That is to say 1 One number, one segment , except 0 The unexpected number did not contribute , Only 0 Yes, there will be 1 The contribution of . Then consider including 0 All interval numbers of are (i + 1) * (n - i) * (1 + (a[i] == 0));
#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,l,r) for(int i=(l);i>=(r);i--)
#define ll long long
#define pii pair<int, int>
#define mset(s,t) memset(s,t,sizeof(t))
#define mcpy(s,t) memcpy(s,t,sizeof(t))
#define fir first
#define pb push_back
#define sec second
#define sortall(x) sort((x).begin(),(x).end())
inline int read () {
int x = 0, f = 0;
char ch = getchar();
while (!isdigit(ch)) f |= (ch=='-'),ch= getchar();
while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
return f?-x:x;
}
template<typename T> void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x >= 10) print(x/10);
putchar(x % 10 + '0');
}
#define int long long
const int N = 2e5 + 10;
int n;
int f[N];
int a[N], b[N];
int sum;
void solve() {
cin >> n;
memset(f, 0, sizeof f);
sum = 0;
for (int i = 1; i<= n ;i ++) {
cin >> a[i];
sum += a[i];
}
for (int i = 1; i<= n ;i ++) {
cin >> b[i];
sum += b[i];
}
f[0] = 1;
for (int i = 1; i<= n; i ++) {
int ndp[N] = {0};
for (int j = 0; j <= sum; j ++) {
if (f[j]) {
ndp[j + a[i]] = ndp[j + b[i]] = 1;
}
}
memcpy(f, ndp,sizeof f);
}
int ans = sum * sum;
for (int i = 0; i <= sum; i ++) {
if (f[i])
ans = min (ans, i * i + (sum - i) * (sum - i));
}
for (int i = 1; i <= n; i ++) {
ans += (a[i] * a[i] + b[i] * b[i]) * (n - 2);
}
cout << ans << endl;
}
signed main () {
int t;
cin >> t;
while (t --) solve();
}
01 knapsack problem , Judge which volume is feasible through backpack . Then the formula can be found as shown in the figure One part is unchanged , Then let a part take the minimum . This is a classic technique . Get the global minimum through traversal
边栏推荐
- 按键精灵采集学习-矿药采集及跑图
- resource 创建包方式
- About some details of final, I have something to say - learn about final CSDN creation clock out from the memory model
- English translation is too difficult? I wrote two translation scripts with crawler in a rage
- 1140_ SiCp learning notes_ Use Newton's method to solve the square root
- After 95, the CV engineer posted the payroll and made up this. It's really fragrant
- 微信小程序中使用wx.showToast()进行界面交互
- 外包幹了三年,廢了...
- 外包干了三年,废了...
- [cloud native] how to give full play to memory advantage of memory database
猜你喜欢
URP - shaders and materials - simple lit
resource 创建包方式
[semantic segmentation] - multi-scale attention
nacos
Leetcode-226. Invert Binary Tree
【斯坦福计网CS144项目】Lab3: TCPSender
1142_ SiCp learning notes_ Functions and processes created by functions_ Linear recursion and iteration
[unity] several ideas about circular motion of objects
[Stanford Jiwang cs144 project] lab4: tcpconnection
外包幹了三年,廢了...
随机推荐
Calculus key and difficult points record part integral + trigonometric function integral
Outsourcing for three years, abandoned
JSON introduction and JS parsing JSON
MobaXterm
Regular e-commerce problems part1
面试结束后,被面试官在朋友圈吐槽了......
[2022 CISCN]初赛 web题目复现
[unity] several ideas about circular motion of objects
leetcode:105. 从前序与中序遍历序列构造二叉树
Talk about seven ways to realize asynchronous programming
Iterable、Collection、List 的常见方法签名以及含义
Operation suggestions for today's spot Silver
Initial experience of teambiion network disk (Alibaba cloud network disk)
leetcode:105. Constructing binary trees from preorder and inorder traversal sequences
外包幹了三年,廢了...
CentOS7下安装PostgreSQL11数据库
解决问题:Unable to connect to Redis
resource 创建包方式
1、 Go knowledge check and remedy + practical course notes youth training camp notes
The annual salary of general test is 15W, and the annual salary of test and development is 30w+. What is the difference between the two?