P1719 最大加权矩形

#include<bits/stdc++.h>
using namespace std;
int a[130][130], s[130][130];
void solve(){
	int n; cin >> n;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			cin >> a[i][j];
			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
		}
	}
	int sum = 0;
	int ans = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			for(int l = 1; l <= i; l++){
				for(int r = 1; r <= j; r++){
					sum = s[i][j] - s[i - l][j] - s[i][j - r] + s[i - l][j - r];
					if(ans <= sum)ans = sum;
				}
			}
		}
	}
	cout << ans << endl;
}
signed main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	solve();
	
	return 0;
} 

P1314 [NOIP 2011 提高组] 聪明的质监员

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200010;
int v[N], w[N], sm[N], cnt[N];
typedef pair<int, int> PII;
PII temp[N];
int n, m, s;
int ans = 1e12;
bool check(int mid){
	memset(sm, 0, sizeof(sm));
	memset(cnt, 0, sizeof(cnt));
	for(int i = 1; i <= n; i++){
		if(w[i] >= mid){
			cnt[i] = cnt[i - 1] + 1;
			sm[i] = sm[i - 1] + v[i];
		}
		else {
			cnt[i] = cnt[i - 1];
			sm[i] = sm[i - 1];
		}
	}
	int sum = 0;
	for(int i = 1; i <= m; i++){
		int x = temp[i].first, y = temp[i].second;
		sum += (sm[y] - sm[x - 1]) * (cnt[y] - cnt[x - 1]);
	}
	if(s > sum){
		ans = min(ans, (s - sum));
		return false;
	}
	else {
		ans = min(ans, (sum - s));
		return true;
	}
}
void solve(){
	cin >> n >> m >> s;
	int minn = 1e12, maxx = -1e12;
	for(int i = 1; i <= n; i++){
		cin >> w[i] >> v[i];
		minn = min(minn, w[i]);
		maxx = max(maxx, w[i]);
	}
	for(int i = 1; i <= m; i++){
		int x, y; cin >> x >> y;
		temp[i] = {x, y};
	}
	int l = minn - 1, r = maxx + 1;
	while(l + 1 != r){
		int mid = l + r >> 1;
		if(check(mid))l = mid;
		else r = mid;
	}
	cout << ans << endl;
}
signed main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	solve();
	
	return 0;
} 

P2367 语文成绩

#include<bits/stdc++.h>
using namespace std;
const int N = 5000010;
int a[N], c[N];
void solve(){
	int n, p; cin >> n >> p;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		c[i] = a[i] - a[i - 1];
	}
	while(p--){
		int x, y, z; cin >> x >> y >> z;
		c[x] += z;
		c[y + 1] -= z;
	}
	int minn = 1e9;
	for(int i = 1; i <= n; i++){
		a[i] = c[i] + a[i - 1];
		minn = min(minn, a[i]);
	}
	cout << minn << endl; 
}
signed main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	solve();
	
	return 0;
} 

P3397 地毯

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int c[N][N], s[N][N];
void solve(){
	int n, m; cin >> n >> m;
	while(m--){
		int x1, y1, x3, y3; cin >> x1 >> y1 >> x3 >> y3;
		c[x1][y1]++;
		c[x1][y3 + 1]--;
		c[x3 + 1][y1]--;
		c[x3 + 1][y3 + 1]++;
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + c[i][j];
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			cout << s[i][j] << " ";
		}
		cout << endl;
	}
} 
signed main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	solve();
	
	return 0;
} 

P3406 海底高铁

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 100010;
int a[N], b[N], c[N], p[N], cha[N];
void solve(){
	int n, m; cin >> n >> m;
	for(int i = 1; i <= m; i++)cin >> p[i];
	for(int i = 1; i < m; i++){
		int x = p[i], y = p[i + 1];
		if(x > y)swap(x, y);
		cha[x]++;
		cha[y]--;
	}
	for(int i = 1; i <= n; i++){
		cha[i] = cha[i - 1] + cha[i];
	}
	for(int i = 1; i < n; i++)cin >> a[i] >> b[i] >> c[i];
	int sum = 0;
	for(int i = 1; i < n; i++){
		if(cha[i] * a[i] >= b[i] * cha[i] + c[i])sum += b[i] * cha[i] + c[i];
		else sum += cha[i] * a[i];
	}
	cout << sum << endl;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    
    
    return 0;
}

P4552 [Poetize6] IncDec Sequence

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 1000010;
int a[N], c[N];
void solve(){
	int n; cin >> n;
	for(int i = 1; i <= n; i++)cin >> a[i];
	for(int i = 1; i <= n; i++){
		c[i] = a[i] - a[i - 1];
	}
	int suma = 0, sumb = 0;
	for(int i = 2; i <= n; i++){
		if(c[i] < 0)suma -= c[i];
		else sumb += c[i];
	}
	cout << max(suma, sumb) << endl << abs(suma - sumb) + 1 << endl;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    
    
    return 0;
}

P1083 [NOIP 2012 提高组] 借教室

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 1000010;
int n, m;
int r[N], d[N], s[N], t[N], c[N], a[N];
bool check(int x){
	memset(c, 0, sizeof(c));
	for(int i = 1; i <= x; i++){
		c[s[i]] += d[i];
		c[t[i] + 1] -= d[i];
	}
	for(int i = 1; i <= n; i++){
		a[i] = a[i - 1] + c[i];
		if(r[i] < a[i])return 0;
	}
	return 1;
}
void solve(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> r[i];
		c[i] = r[i] - r[i - 1];
	}
	for(int i = 1; i <= m; i++){
		cin >> d[i] >> s[i] >> t[i];
	}
	if(check(m)){
		cout << 0 << endl;
		return;
	}
	int l = 0, r = m + 1;
	while(l + 1 != r){
		int mid = l + r >> 1;
		if(check(mid))l = mid;
		else r = mid;
	}
	cout << -1 << endl << r << endl;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    
    
    return 0;
}