akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
using namespace std;

int main() {
	int A, B, M, * a, * b, x, y, c, minA = pow(10, 5), minB = pow(10, 5), p = 3 * pow(10, 5), tmp = 0;

	cin >> A >> B >> M;;

	a = new int[A];
	b = new int[B];

	for (int i = 0; i < A; i++) {
		cin >> a[i];
		if (minA > a[i]) { minA = a[i]; }
	}

	for (int i = 0; i < B; i++) {
		cin >> b[i];
		if (minB > b[i]) { minB = b[i]; }
	}

	for (int i = 0; i < M; i++) {
		cin >> x >> y >> c;
		tmp = a[x -1] + b[y -1] - c;
		if (p > tmp) {
			p = tmp;
		}
	}

	if (minA + minB < p) { p = minA + minB; }

	cout << p;

	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>

int main(void)
{
	int length[5], k, i;
	for(i = 0; i < 5; i++) scanf ("%d", &length[i]);
	scanf ("%d", &k);
	if (length[4] - length[0] <= k) printf ("Yay!\n");
	else printf (":(\n");
	return (0);
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;

const double PI = acos(-1);
const int inf = 2e9;
const ll INF = 2e18;
const ll MOD = 1e9+7;

#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
#define REP(i,n) for (int i = 0; i<n; i++)
#define ALL(a) begin(a), end(a)

int main (void) {
    int N;
    cin>>N;
    map<int,int> mp;
    REP(i,N) {
        int x;
        cin>>x;
        for (int t=x-1;t<=x+1;t++) {
            if (mp.find(t)!=mp.end()) mp[t]++;
            else mp[t] = 1;
        }
    }
    int ans = -1;
    for (auto m:mp) {
        ans = max(ans,m.second);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4736
#include <stdio.h>
#include <stdlib.h>

int	kaijo(int nb)
{
	int sum = 1;
	while (nb > 0)
	{
		sum *= nb;
		nb--;
	}
	return (sum);
}

int main(void)
{
	int N;
	scanf("%d", &N);
	int i = 1;
	int p[N + 1], q[N + 1];
	for (i = 0; i < N; i++)
		scanf("%d", &p[i]);
	for (i = 0; i < N; i++)
		scanf("%d", &q[i]);
	int ans1 = 1;
	int ans2 = 1;
	int j,pre1,pre2;
	for (i = 0; i < N - 1; i++)
	{
		pre1 = 0;
		pre2 = 0;
		for (j = 0; j < i;j++)
		{
			if (p[j] < p[i])
				pre1++;
			if (q[j] < q[i])
				pre2++;
		}
		ans1 += kaijo(N-i-1) * (p[i] - 1 - pre1);
		ans2 += kaijo(N-i-1) * (q[i] - 1 - pre2);
	}
	printf("%d\n", abs(ans1 - ans2));
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define show(x) cout<<#x<<" "<<x<<endl
#define rep(i,n) for(int i=0;i<n;i++)
#define fs first
#define sc second
#define pb push_back
#define all(c) c.begin(),c.end()
using namespace std;
typedef pair<double,double> P;
typedef pair<int,int> Pi;
typedef pair<double,Pi> dP;
int x[100],y[100];
double dis(P p,P q){
	return sqrt((p.fs-q.fs)*(p.fs-q.fs)+(p.sc-q.sc)*(p.sc-q.sc));
}
int main(){
	while(true){
		int N;
		cin>>N;
		if(N==0) break;
		rep(i,N) cin>>x[i]>>y[i];
		vector<int> ys;
		rep(i,N) ys.pb(y[i]);
		sort(all(ys));
		ys.erase(unique(all(ys)),ys.end());
		vector<P> ps;
		rep(i,N-1){
			for(int yy:ys){
				if(y[i]<yy&&yy<y[i+1]){
					double xx=x[i]+(double)(x[i+1]-x[i])*(yy-y[i])/(y[i+1]-y[i]);
					ps.pb(P(xx,yy));
				}
				if(y[i]>yy&&yy>y[i+1]){
					double xx=x[i]+(double)(x[i+1]-x[i])*(y[i]-yy)/(y[i]-y[i+1]);
					ps.pb(P(xx,yy));
				}
			}
		}
		rep(i,N) ps.pb(P(x[i],y[i]));
		sort(all(ps));
		int M=ps.size();
//		show(M);
//		rep(i,M) cout<<"    "<<ps[i].fs<<" "<<ps[i].sc<<endl;
		priority_queue<dP,vector<dP>,greater<dP> > que;
		map<Pi,double> mp;
		que.push(dP(0,Pi(0,M-1)));
		mp[Pi(0,M-1)]=0;
		while(!que.empty()){
			dP dp=que.top();
			que.pop();
			double d=dp.fs;
			Pi p=dp.sc;
			if(mp.count(p)&&mp[p]<d) continue;
			int x=p.fs,y=p.sc;
			for(int di=-1;di<=1;di++) for(int dj=-1;dj<=1;dj++){
				int nx=x+di,ny=y+dj;
				if(!(0<=nx&&nx<M&&0<=ny&&ny<M)) continue;
				if(ps[nx].sc!=ps[ny].sc) continue;
				double dist=dis(ps[x],ps[nx])+dis(ps[y],ps[ny]);
				Pi np=Pi(nx,ny);
				if(!mp.count(np)||mp[np]>d+dist){
					mp[np]=d+dist;
					que.push(dP(d+dist,np));
				}
			}
		}
		double ans=1e9;
		rep(i,M) ans=min(ans,mp[Pi(i,i)]);
		printf("%.12f\n",ans);
	}
}

Measured memory_bytes: 7164
// "header" {{{
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <string>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cstring>
#include <iomanip>
#include <tuple>

using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int> 
#define int int64_t
#define Fixed fixed << setprecision(10)
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const long long mod = 1000000007;

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;

inline double sqrt( const double &x) 
{
	double         xHalf = 0.5 * x;
	int64_t  tmp   = 0x5FE6EB50C7B537AAl - ( *(int64_t*)&x >> 1);
	double         xRes  = * (double*)&tmp;

	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	return xRes * x;
}
// }}}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,m;
	cin >> n >> m;
	vector<int> s(m),p(m);
	rep(i,m){
		int k;
		cin >> k;
		rep(j,k){
			int a;
			cin >> a;
			s[i] |= (1 << (a-1));
		}
	}
	rep(i,m){
		cin >> p[i];
	}

	int cnt = 0;

	for(int bit = 0;bit < (1 << n);++bit){
		int flg = true;
		rep(i,m){
			if(__builtin_popcount(bit & s[i]) % 2 != p[i]){
				flg = false;
				break;
			}
		}
		if(flg) ++cnt;
	}

	cout << cnt << '\n';

	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
	string N;

	cin >> N;
	string a(N.substr(0, 1));
	string b(N.substr(2, 1));

	if (a == b) {
		cout << "Yes" << endl;

	}
	else
	{
		cout << "No" << endl;
	}
	system("pause");
	return 0;

}

Measured memory_bytes: 504
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=1<<20;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<20> st;

int N;
int S[202020];
int Q;
vector<int> ev[202020];
int dp[202020];


void solve() {
	int i,j,k,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		dp[0]+=x;
		if(x==1) S[i+1]=S[i]-1;
		else S[i+1]=S[i]+1;
	}
	
	
	FOR(i,N+1) {
		if(i) dp[i]=1<<20;
		st.update(i,dp[i]+(S[N]-S[i]));
	}
	
	cin>>Q;
	FOR(i,Q) {
		cin>>x>>y;
		ev[x].push_back(y);
	}
	for(i=1;i<=N;i++) {
		FORR(r,ev[i]) {
			x = min(dp[i-1]+(S[r]-S[i-1]),st.getval(i,r+1) - (S[N]-S[r]));
			if(x<dp[r]) {
				dp[r]=x;
				st.update(r,dp[r]+(S[N]-S[r]));
			}
		}
		dp[i]=min(dp[i],dp[i-1]);
		
	}
	cout<<*min_element(dp,dp+N+1)<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 18688
# -*- coding: utf-8 -*-

import numpy as np

EDPC = "https://atcoder.jp/contests/dp/"
TDPC = "https://atcoder.jp/contests/tdpc/tasks"

############### TESTCASE ###############
test = ""
#test = \
"""
3
10 40 70
20 50 80
30 60 90
ans 210
"""

"""
1
100 10 1
ans 100
"""

"""
7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1
ans 46
8, 8, 5, 8, 8, 4, 7 -> 48
8, 8, 5, 7, 8, 3, 7 -> 46
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################  
n = int(input2())
a = np.array([list(map(int, input2().split())) for i in range(n)])  
########## Non_Numpy_solution ##########

arr = a
dp = [[0, 0, 0] for _ in range(n)]
dp[0] = arr[0]
for i in range(1, n):
    dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + arr[i][0]
    dp[i][1] = max(dp[i - 1][2], dp[i - 1][0]) + arr[i][1]
    dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + arr[i][2]
print (max(dp[-1]))



Measured memory_bytes: 41792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using VS = vector<string>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "-----------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause") //comment out this on AOJ.
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T>inline istream& operator>>(istream& is, deque<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

int n;
VI a;
vector<VI> memo;
int solve(int x, int t) {
    if (memo[x][t] != -1)return memo[x][t];
    int ret = abs(a[n + 1] - a[x]);
    if (t == 0)FOR(i, x + 1, n + 1)chmax(ret, solve(i, 1));
    else FOR(i, x + 1, n + 1)chmin(ret, solve(i, 0));
    return memo[x][t] = ret;
}

int main() {
    init();

    cin >> n;
    a.resize(n + 2); cin >> a;
    memo = defvec<int>(-1, n + 2, 2);
    cout << solve(1, 0) << "\n";
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++)
		cin>>a[i];
	sort(a,a+n);
	int ans=0;
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			int ind = lower_bound(a+j+1,a+n,a[i]+a[j]) - a;
			ans+=max(ind-j-1,0);
		}
	}
	cout<<ans;
}




Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**7)
N,M=list(map(int,raw_input().split()))

nl=[[] for i in range(N+1)]
for i in range(M):
	x,y=map(int,raw_input().split())
	nl[x].append(y)
	nl[y].append(x)	
#print nl


def dfs(v):
	F[v]=1
	for i in nl[v]:
		if color[v]=="w" and color[i]==0:
			color[i]="b"
		elif color[v]=="b" and color[i]==0:
			color[i]="w"				
		elif color[v]==color[i]:
			#２部グラフではない
			print N*(N-1)/2-M
			sys.exit()
		else:
			continue
		#print v,i,color,F
		
		if F[i]==0:
			dfs(i)


F=[0]*(N+1)
color=[0]*(N+1)
color[1]="w"
dfs(1)

#２部グラフの場合
print color.count("b")*color.count("w")-M




Measured memory_bytes: 32200
#include <iostream>
#include <vector>
using namespace std;

int main()
{
	int N = 0;
	cin >> N;
	vector<int> dv(N, 0);
	for (int i = 0; i < N; ++i)
		cin >> dv[i];

	int sum = 0;
	for (int i = 0; i < N - 1; ++i)
		for (int j = i + 1; j < N; ++j)
		{
			sum += dv[i] * dv[j];
		}

	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for(long long i=0;i<(long long)(n);i++)
#define rep2(i, s, n) for(long long i=(s);i<(long long)(n);i++)
#define all(v) v.begin(), v.end()

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<ll, ll>;

const ll INF = (1LL<<60);

int main(){

    ll n, m; cin >> n >> m;

    ll l, r;
    cin >> l >> r;
    ll inl, inr;
    rep2(i, 1, m){
        cin >> inl >> inr;
        l = max(l, inl);
        r = min(r, inr);
    }

    ll ans = r-l+1;
    if(l>r) ans = 0;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int n; int ans; int t;
vector <pair<int, int>> v;

int main() {

	
	cin >> n;
	v.resize(n);
	
	for (int i = 0; i < n; i++) {
		int c, l;
		cin >> c >> l;
		v[i].second = c - l; v[i].first = c + l;
	}

	sort(v.begin(), v.end());

	t = -10000000000;


	for (int i = 0; i < n; i++) {
		if (t <= v[i].second) {
			ans++;
			t = v[i].first;
		}
	}

	cout << ans << endl;

}

Measured memory_bytes: 3956
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 25;

inline bool compare(const pair<int, int> &a, const pair<int, int> &b) {
	if (a.second == b.second) {
		return a.first > b.first;
	}
	return a.second < b.second;
}

pair<int, int> ar[MAXN];

int N;

int main () {

	int cur = 0;

	scanf("%d", &N);

	for( int i=1 ; i <= N ; i++ ) {
		scanf("%d%d", &ar[i].first, &ar[i].second);
	}

	sort(ar + 1, ar + N + 1, compare);

	for( int i=1 ; i <= N ; i++ ) {

		// cerr << ar[i].first << " " << ar[i].second << " -> " << cur << endl;
		
		cur += ar[i].first;

		if (cur > ar[i].second) {
			puts("No");
			return 0;
		}
	}

	puts("Yes");
	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;

int main(){
    int a,b,c;
    cin >>a >> b>> c;

    int ans=0;
    if(a==b) ans++;
    if(b==c) ans++;
    if(c==a) ans++;

    if(ans==1){
        cout <<"Yes"<<endl;
    }else{
        cout <<"No"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>

typedef struct point{double x,y;}point;

void kochcurve(int n,point a,point b){
    if(n==0) return;
    point s,t,u;
    double p=3.14159265*60.0/180.0;

    s.x=(2.0*a.x+1.0*b.x)/3.0;
    s.y=(2.0*a.y+1.0*b.y)/3.0;
    t.x=(1.0*a.x+2.0*b.x)/3.0;
    t.y=(1.0*a.y+2.0*b.y)/3.0;
    u.x=(t.x-s.x)*cos(p)-(t.y-s.y)*sin(p)+s.x;
    u.y=(t.x-s.x)*sin(p)+(t.y-s.y)*cos(p)+s.y;

    kochcurve(n-1,a,s);
    printf("%.8f %.8f\n",s.x,s.y);
    kochcurve(n-1,s,u);
    printf("%.8f %.8f\n",u.x,u.y);
    kochcurve(n-1,u,t);
    printf("%.8f %.8f\n",t.x,t.y);
    kochcurve(n-1,t,b);
}

int main(){
    point a,b;
    int n;
    scanf("%d",&n);

    a.x=0;
    a.y=0;
    b.x=100;
    b.y=0;

    printf("%.8f %.8f\n",a.x,a.y);
    kochcurve(n,a,b);
    printf("%.8f %.8f\n",b.x,b.y);
    return 0;
} 


Measured memory_bytes: 2052
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i < (n); i++)
#define lower(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
using namespace std;
using ll = long long;
int INF = 1001001001;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  sort(a.begin(), a.end());
  a.erase(unique(a.begin(), a.end()), a.end());
  if(a.size() == n) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 3964
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const long long INF = 1LL << 60;

long long h[110000];
long long dp[110000];

int main(){
  int N, K; cin>>N>>K;
  for(int i=0; i<N; i++) cin>>h[i];
  for(int i=0; i<110000; i++) dp[i] = INF;
  dp[0]=0;
  for(int i=0; i<N; i++){
    for(int j=1; j<=K; j++){
      chmin(dp[i+j], dp[i]+abs(h[i]-h[i+j]));
    }
  }
  cout<<dp[N-1]<<endl;
}


Measured memory_bytes: 1920
N = int(input())
ans = [0]*(N+1)
for x in range(1,105):
    for y in range(1,105):
        for z in range(1,105):
            tmp = x**2 + y**2 + z**2 +x*y + y*z + z*x
            if tmp > N:
                continue
            ans[tmp]+=1
for i in range(1,N+1):
    print(ans[i])


Measured memory_bytes: 8984
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef double dd;
#define all(v) v.begin(),v.end()
#define endl "\n"
#define clr(n, r) memset(n,r,sizeof(n));

void fast() {
    cin.tie(0);
    cin.sync_with_stdio(0);
}
const int MAX=1e5+10;
int n,a[MAX],b[MAX],c[MAX],dp[MAX][3];
int ans(int i,int prev){
    if(i==n)return 0;
    int path1=0,path2=0,path3=0;
    int &ret=dp[i][prev];
    if(prev!=-1&&ret!=-1)return ret;
    if(prev!=0){
        path1=a[i]+ans(i+1,0);
    }
    if(prev!=1){
        path2=b[i]+ans(i+1,1);
    }
    if(prev!=2){
        path3=c[i]+ans(i+1,2);
    }
    return ret=max(path1,max(path2,path3));
}

int main() {
    fast();
    cin>>n;
    for (int i = 0; i < n; ++i) {
    cin>>a[i]>>b[i]>>c[i];
    }
    clr(dp,-1);
    cout<<ans(0,-1);
}


Measured memory_bytes: 8832
from itertools import combinations_with_replacement

N,M,Q = map(int, input().split())
matrix = [list(map(int, input().split())) for i in range(Q)]

def evaluate(A, matrix):
  total = 0
  for a,b,c,d in matrix:
    if (A[b - 1] - A[a - 1]) == c:
      total += d
  return total

print(max([evaluate(A, matrix) for A in combinations_with_replacement(range(1, M + 1), N)]))

Measured memory_bytes: 74676
#include <iostream>
#include <algorithm>
#include <time.h>
#include <ctime>
#define flush fflush(stdout)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pl;
const int mod = (int)1e9 + 7, INF = (int)1e9;
const int di[4] = { 1,0,-1,0 }, dj[4] = { 0,1,0,-1 };


int d, c[28], s[370][28];

int score(int* t) {
    int i, j, b[28], ans;

    for (i = 0; i < 26; i++) {
        b[i] = 1;
    }

    ans = 0;
    for (i = 0; i < d; i++) {
        ans += s[i][t[i]];
        b[t[i]] = 0;
        for (j = 0; j < 26; j++) {
            ans -= c[j] * b[j];
            b[j]++;
        }
    }

    return ans;
}

int main(void) {
    int i, j;

    clock_t start = clock(), end;
    double rtime;

    scanf("%d", &d);
    for (i = 0; i < 26; i++) {
        scanf("%d", &c[i]);
    }
    for (i = 0; i < d; i++) for (j = 0; j < 26; j++) {
        scanf("%d", &s[i][j]);
    }

    int t[370], scmax, scmi;

    for (i = 0; i < d; i++) {
        scmax = 0;
        scmi = 0;
        for (j = 0; j < 26; j++) {
            if (scmax < s[i][j]) {
                scmax = s[i][j];
                scmi = j;
            }
        }
        t[i] = scmi;
    }

    int before = score(t), after, chd, cht, bt;

    srand(time(nullptr));

    while (1) {
        end = clock();
        rtime = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000.0;
        if (rtime > 1950) {
            break;
        }

        chd = rand() % d;
        cht = rand() % 26;

        bt = t[chd];
        t[chd] = cht;

        after = score(t);

        if (after < before) {
            t[chd] = bt;
        }
        else {
            before = after;
        }
    }

    for (i = 0; i < d; i++) {
        printf("%d\n", t[i] + 1);
    }
    
    return 0;
}

Measured memory_bytes: 3860
from collections import deque

H, W = map(int, input().split())
A = [input() for _ in range(H)]
visited = [[-1] * W for _ in range(H)]

que = deque([])
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            que.append([i, j])
            visited[i][j] = 0


while len(que):
    py, px = que.popleft()
    dy = [0, 1, 0, -1]
    dx = [1, 0, -1, 0]
    for i, j in zip(dy, dx):
        ny = py + i
        nx = px + j
        if nx < 0 or ny < 0 or nx >= W or ny >= H:
            continue
        if A[ny][nx] == '#':
            continue
        if visited[ny][nx] >= 0:
            continue
        visited[ny][nx] = visited[py][px] + 1
        que.append([ny, nx])

cnt = 0
for i in range(H):
    cnt = max(cnt, max(visited[i]))

print(cnt)


Measured memory_bytes: 141276
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define min(a,b) a<b ? a:b
#define max(a, b) a < b ? b : a
#define IOS                           \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0)
#define endl "\n"
#define pb push_back
#define pi 3.14159265358979323846

// int explore(vector<vector<int>> &adj,int x,int y,vector<int> &visited)
// {
//     if(x==y)
//     return 1;
//     visited[x]=1;
//     for(int i=0;i<adj[x].size();i++)
//     {
//         if(!visited[adj[x][i]])
//         {
//             if(explore(adj,adj[x][i],y,visited))
//             return 1;
//         }
//     }
//     return 0;
// }
bool valley(int p[], int k)
{
    if (p[k] < p[k - 1] && p[k] < p[k + 1])
        return true;
    return false;
}
bool peak(int p[], int k)
{
    if (p[k] > p[k - 1] && p[k] > p[k + 1])
        return true;
    return false;
}

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b); 
}
int const N=10000007;
int prime[N];
// for(int i=1;i<=n;i++)
//         {
//             if(a[i]==maxi)
//             {
//                 ctr++;
//                 ans=max(ans,ctr);
//             }
//             else
//             ctr=0;
//         }
int32_t main() 
{
    // IOS;
    // int t;
    // cin>>t;
    // while(t--)
    // {
            int n;
            cin>>n;
            int a[n];
            int ctr=0;
            for(int i=0;i<n;i++)
            {
                cin>>a[i];
            }
            int maxi = INT_MIN;
            for(int i=0;i<n;i++)
            {
                maxi=max(maxi,a[i]);
                ctr+=maxi-a[i];
            }
            cout<<ctr;


    // }

}

Measured memory_bytes: 5140
#include <bits/stdc++.h>
using namespace std;

#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false
#define INVSORT(c) sort((c).begin(), (c).end(), greater<pair<int, int>>());

int main()
{
    int n,m;
    cin>>n>>m;
    int ans=0;
    rep(i,n){
        int temp;
        cin>>temp;
        ans+=min(temp*2,abs(m-temp)*2 );
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	items := make(map[string]struct{})
	var item string
	for i := 0; i < n; i++ {
		fmt.Scan(&item)
		items[item] = struct{}{}
	}
	num := len(items)
	fmt.Println(num)
}


Measured memory_bytes: 18396
A = []
for i in range(3):
    A.append(list(map(int, input().split())))
N = int(input())
for i in range(N):
    b = int(input())
    for j in range(3):
        if b in A[j]:
            A[j][A[j].index(b)] = 0

if (sum(A[0]) == 0) or (sum(A[1]) == 0) or (sum(A[2]) == 0):
    print('Yes')
elif(A[0][0] + A[1][0] + A[2][0] == 0) or (A[0][1] + A[1][1] + A[2][1] == 0) or (A[0][2] + A[1][2] + A[2][2] == 0):
    print('Yes')
elif(A[0][0] + A[1][1] + A[2][2] == 0) or (A[0][2] + A[1][1] + A[2][0] == 0):
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
#include <bits/stdc++.h>

#define rep(i, n) for(int i=0; i < n; i++)
#define REP(i, n, m) for(int i=n; i < m; i++)
#define reps(i, n) for(int i=1; i <= n; i++)
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)

using namespace std;
using ll=long long;

ll mod=1000000007;

const ll INF = 1LL << 60;

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}

ll gcd(int x,int y){
  if(!(x%y))return y;
  else return gcd(y,x%y);
}

int main() {
  int k;cin>>k;
  ll sum=0;
  reps(i,k)reps(j,k)reps(l,k){
    sum+=gcd(i,gcd(j,l));
  }
  cout << sum;
}

Measured memory_bytes: 3632
#include<iostream>
using namespace std;
int main()
{ 
     int a,b,c;
     cin>>a>>b;
      if(a+b==3)
     { 
         cout<<"3";
     }
     else if(a+b==5)
     { 
         cout<<"1";
     } 
     else if(a+b==4)
     {
         cout<<"2";
     }
      
     return 0;
     } 
     

Measured memory_bytes: 3632
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;
typedef long long ll;
typedef pair<int, int> Pint;
typedef pair<ll, ll> Pll;
#define rep(begin, i, end) for (ll i = begin; i < (ll)(end); i++)
#define all(v) v.begin(), v.end()
const int MOD = 998244353;

ll pow(ll a, ll b)
{
    if (a == 0)
    {
        return 0;
    }
    if (b == 0)
    {
        return 1;
    }
    if (b % 2 == 0)
    {
        return (pow(a, b / 2) * pow(a, b / 2)) % MOD;
    }
    else
    {
        return (a * pow(a, b - 1)) % MOD;
    }
}

int main()
{
    ll N;
    cin >> N;
    map<ll, ll> mp;
    vector<ll> d(N, 0);
    rep(0, i, N)
    {
        cin >> d.at(i);
        mp[d.at(i)]++;
    }

    if (mp[0] != 1 || d.at(0) != 0)
    {
        cout << 0 << endl;
        return 0;
    }

    sort(all(d));
    rep(1, i, N)
    {
        if ((d.at(i) - d.at(i - 1) == 0) || (d.at(i) - d.at(i - 1) == 1))
        {
            continue;
        }
        else
        {
            cout << 0 << endl;
            return 0;
        }
    }

    ll ans = 1, count = 1;
    rep(1, i, N)
    {
        ans *= pow(mp[i - 1], mp[i]);
        ans %= MOD;
        count += mp[i];
        if (count == N)
        {
            break;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 10224
#include<bits/stdc++.h>

#define endl '\n'

using namespace std;

int main(){

  cin.tie(0);     // cout と cin の同期を切る
  ios::sync_with_stdio(false);  /* cの stdioストリーム (printfとか)と*/


  int N,Y;

  cin>>N>>Y;

  for(int i=0;i<=N;i++){
    for(int j=0;j<=N;j++){

      if(i>=0&&j>=0&&(N-(i+j))>=0){
	if(i*1000+j*5000+10000*(N-(i+j))==Y){
	  cout<<(N-(i+j))<<" "<<j<<" "<<i<<endl;
	  return 0;
	}
      }
    }
  }

  cout<<-1<<" "<<-1<<" "<<-1<<endl;
  
    
  return 0;

}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=200005;
struct bag{
    int x,y;
}p[maxn];
bool operator < (bag a,bag b){
    if(a.x==b.x)return a.y<b.y;
    return a.x<b.x;
}
int n,Rmax,Rmin,Bmax,Bmin;
int main(){
    long long ans=1e18;
    scanf("%d",&n);
    if(n==1){
        cout<<0<<endl;return 0;
    }
    for(int i=0;i<n;i++){
        scanf("%d%d",&p[i].x,&p[i].y);
        if(p[i].x>p[i].y){
            int k=p[i].x;
            p[i].x=p[i].y;
            p[i].y=k;
        }
    }
    sort(p,p+n);
    int Max=p[0].y,Min=p[0].x,_max=0,_min=0;
    for(int i=1;i<n;i++){
        if(p[i].x<=Min&&p[i].y>=Max){
            Min=p[i].x;Max=p[i].y;
            _max=i;_min=i;
        }
        else if(p[i].x<Min){
            Min=p[i].x;
            _min=i;
        }else if(p[i].y>Max){
            Max=p[i].y;
            _max=i;
        }
    }
    Rmax=Max;Bmin=Min;
    Rmin=p[_min].y;Bmax=p[_max].x;
    for(int i=0;i<n;i++){
        Rmin=min(Rmin,p[i].y);
        Bmax=max(Bmax,p[i].x);
    }
    ans=(long long)(Rmax-Rmin)*(Bmax-Bmin);
    if(_max!=_min){
        Bmax=Max;Bmin=Min;
        Rmax=max(p[n-1].x,p[0].y);
        int premin=p[0].y;
        Rmin=min(p[0].y,p[1].x);
        //sort(p,p+n);
        long long ans0=Rmax-Rmin;
        for(int i=1;i<n-1;i++){
            Rmax=max(p[i].y,Rmax);
            Rmin=min(min(premin,p[i].y),p[i+1].x);
            premin=min(premin,p[i].y);
            if(Rmax-Rmin<ans0)ans0=Rmax-Rmin;
        }
        ans0*=Bmax-Bmin;
        ans=min(ans,ans0);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1920
#include <bits/stdc++.h>

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
typedef long long ll;

ll gcd(ll x, ll y) {
    if (y == 0) {
        return x;
    }
    return gcd(y, x % y);
}

vector<pair<ll, int >> factorize(ll n) {
    vector<pair<ll, int >> res;

    for (ll i = 2; i * i <= n; i++) {
        if (n % i != 0) {
            continue;
        }
        res.emplace_back(n, 0);
        while (n % i == 0) {
            n /= i;
            res.back().second++;
        }
    }

    if (n != 1) res.emplace_back(n, 1);
    return res;

}

int main() {
    ll a, b;
    cin >> a >> b;
    ll g = gcd(a, b);
    auto divisor = factorize(g);
    cout << divisor.size() + 1 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  vector<int> p(3);
  for(int i=0;i<3;i++){
    cin>>p.at(i);
  }
  sort(p.begin(),p.end());
  reverse(p.begin(),p.end());
  cout<<p.at(0)*10+p.at(1)+p.at(2)<<endl;
  return 0;
}

Measured memory_bytes: 256
import sys

#fin = open("test.txt", "r")
fin = sys.stdin

n = int(fin.readline())

taros_score = 0
hanakos_score = 0
winner_points = 3
draw_points = 1

for i in range(n):
	s0, s1 = fin.readline().split()

	if s0 > s1:
		taros_score += winner_points
	elif s0 < s1:
		hanakos_score += winner_points
	else:
		taros_score += draw_points
		hanakos_score += draw_points

print(taros_score, hanakos_score)

Measured memory_bytes: 7616
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <cmath>
 
#define rep(i,n) for(int i = 0;i < (n);i++)
#define all(x) (x).begin(),(x).end()
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)

using namespace std;

typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<pair<int, int> > vpi;
typedef vector<pair<ll, ll> > vpl;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int k, t;
  cin >> k >> t;
  vi a(t);
  int sum = 0;
  rep(i,t){
    cin >> a[i];
    sum += a[i];
  }
  sort(a.rbegin(),a.rend());
  if(a[0]-1 -(sum-a[0]) <= 0){
    cout << 0 << endl;
  }else{
    cout << a[0]-1 -(sum-a[0]) << endl;
  }
	return 0;
}


Measured memory_bytes: 384
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def rec(i, A, ok_v):
    # print(i, A, ok_v)
    if ok_v <= 0:
        return -1, -1
    if i == len(A) - 1:
        if A[-1] > ok_v:
            return -1, -1
        else:
            return A[-1], A[-1]
    # if i > 70:
    #     child, ans = rec(i + 1, A, -1)
    #     if child == ans == -1:
    #         return -1, -1
    #     else:
    #         return child + A[i], child + A[i] + ans
    child, ans = rec(i+1, A, (ok_v - A[i]) * 2)
    # print("\t", i, child, ans)
    if child == ans == -1:
        return -1, -1
    num_v = min(ok_v, child + A[i])
    return num_v, ans + num_v


def main() -> None:
    N = int(input())
    A = [int(x) for x in input().split()]
    if N == 0:
        print(1 if A[0] == 1 else -1)
        return
    elif A[0] != 0:
        print(-1)
        return

    _, ans = rec(1, A, 2)
    print(ans + 1 if ans > 0 else -1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 761076
N, M = map(int, input().split())
ac = [0]*N
wa = [0]*N
for i in range(M):
    p, s = input().split()
    if s == 'AC':
        ac[int(p)-1] = 1
    elif s == 'WA' and ac[int(p)-1] == 0:
        wa[int(p)-1] += 1

nwa = sum([ wa[i] for i in range(N) if ac[i] == 1])
print(sum(ac), nwa)

Measured memory_bytes: 5424
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin>>N;
  vector<pair<int,int>> p(N);
  vector<vector<int>> yoko(100000);
  vector<int> s(100000);
  for(int i=0;i<N;i++){
    int a,b;
    cin>>a>>b;
    a--,b--;
    p[i]=make_pair(a,b);
    yoko[b].push_back(a);
    s[b]++;
  }
  vector<vector<int>> G(100000);
  sort(p.begin(),p.end());
  for(int i=1;i<N;i++){
    int a,b,c,d;
    tie(a,b)=p[i-1];
    tie(c,d)=p[i];
    if(a==c){
      G[b].push_back(d);
      G[d].push_back(b);
      }
    
  }
  int64_t Z=0;
  vector<int> seen(100000);
  for(int i=0;i<100000;i++){
    if(seen[i]||s[i]==0){
      continue;
    }
    int64_t A=0;
    set<int> s;
    queue<int> q;
    q.push(i);
    seen[i]=1;
    while(!q.empty()){
      int a=q.front();
      q.pop();
      A++;
      for(auto x:G[a]){
        if(!seen[x]){
          seen[x]=1;
          q.push(x);
        }
      }
      for(auto x:yoko[a]){
        s.insert(x);
      }
    }
    int64_t M=s.size();
    Z+=A*M;
  }
  Z-=N;
  cout<<Z<<endl;
}

Measured memory_bytes: 14984
N = int(input())
A = []
B = []

for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

count = 0
for i in range(N):
    # print(count+A[N-i -1], B[N-i -1], (count+A[N-i -1]) % B[N-i -1])
    if (count+A[N-i -1]) % B[N-i -1] == 0:
        continue
    else:
        count += B[N-i -1] - ((count+A[N-i -1]) % B[N-i -1])
print(count)

Measured memory_bytes: 57432
{-# LANGUAGE FlexibleInstances    #-}
{-# LANGUAGE TypeSynonymInstances #-}

import           Control.Applicative
import           Control.DeepSeq
import           Control.Monad
import           Control.Monad.ST
import qualified Data.Array                  as A
import qualified Data.Array.IArray           as IA
import qualified Data.Array.IO               as AI
import qualified Data.Array.MArray           as MA
import qualified Data.Array.ST               as STA
import qualified Data.Array.Unboxed          as AU
import           Data.Bits
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import qualified Data.Graph                  as G
import           Data.Int
import qualified Data.IntMap                 as IM
import qualified Data.IntSet                 as IS
import           Data.List
import qualified Data.Map.Strict             as M
import           Data.Maybe
import           Data.Ord
import qualified Data.Sequence               as SQ
import qualified Data.Set                    as S
import           Data.Time
import qualified Data.Tree                   as T
import qualified Data.Vector                 as V
import qualified Data.Vector.Mutable         as VM
import qualified Data.Vector.Unboxed         as VU
import qualified Data.Vector.Unboxed.Mutable as VUM

readInt :: IO [Int]
readInt = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

readInts :: Int -> IO [[Int]]
readInts n = replicateM n readInt

readInteger :: IO [Integer]
readInteger = map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine

readIntegers :: Int -> IO [[Integer]]
readIntegers n = replicateM n readInteger

readString :: IO [String]
readString = map BS.unpack . BS.words <$> BS.getLine

readStrings :: Int -> IO [[String]]
readStrings n = replicateM n <$> readString

toPair :: [a] -> (a, a)
toPair [x, y] = (x, y)

count :: Eq a => a -> [a] -> Int
count a as = length $ filter (== a) as

put :: Show a => a -> IO ()
put = putStr . show

putLn :: Show a => a -> IO ()
putLn = print

putList :: Show a => [a] -> IO ()
putList [n] = put n
putList (n:ns) = do
  put n
  putStr " "
  putList ns

putStrList :: [String] -> IO ()
putStrList [n] = putStr n
putStrList (n:ns) = do
  putStr n
  putStr " "
  putStrList ns

main = do
  a <- getLine
  b <- getLine
  c <- getLine
  putStrLn $ [a !! 0, b !! 1, c !! 2]


Measured memory_bytes: 380
N = int(input())
S = input()
MOD = 10**9+7

if S[0]=="W" or S[-1]=="W":
    print(0)
else:
    l = [None]*(2*N)
    l[0] = 0
    for i in range(1, 2*N):
        l[i] = (0 if l[i-1] else 1) if S[i]==S[i-1] else (1 if l[i-1] else 0)

    facN = 1
    for i in range(N):
        facN *= i+1
        facN %= MOD

    ans = 0
    if sum(l)==N:
        b = 0
        ans = facN
        for i in l[::-1]:
            if i:
                b += 1
            else:
                ans *= b
                ans %= MOD
                b -= 1
    print(ans)


Measured memory_bytes: 12212
//
// C - 高橋君とカード / Tak and Cards
//

#include <iostream>

using namespace std;
using LL = long long;

LL dp[51][51][2501];
int xs[51];

int main() {

    int N, A;
    cin >> N >> A;

    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        xs[i] = x;
    }

    dp[0][0][0] = 1;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            for (int k = 0; k <= 2500 - xs[i]; k++) {
                dp[i + 1][j][k] += dp[i][j][k];
                dp[i + 1][j + 1][k + xs[i]] += dp[i][j][k];
            }
        }
    }

    LL ans = 0;

    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= 2500; j++) {
            if ((double) j / i == A) {
                ans += dp[N][i][j];
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 49152
#define _CRT_SECURE_NO_WARNINGS

#pragma GCC optimize("O3")

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <cstring>
#include <numeric>
#include <set>
#include <queue>
#include <deque>
#include <array>
#include <string>
#include <cmath>
#include <random>
#include <ctime>
#include <map>
#include <functional>
#include <bitset>
#include <complex>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()
#define pb push_back

using namespace std;
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using ld = long double;

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, W;
	cin >> n >> W;
	vi w(n), v(n);
	for (int i = 0; i < n; i++) {
		cin >> w[i] >> v[i];
	}
	const ll inf = 1e18 + 228;
	int C = n * 1000;
	vector<ll> dp(C + 1, inf);
	dp[0] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = C; j >= 0; j--) {
			if (j - v[i] >= 0) {
				dp[j] = min(dp[j], dp[j - v[i]] + w[i]);
			}
		}
	}
	for (int i = C; i >= 0; i--) {
		if (dp[i] <= W) {
			cout << i;
			return 0;
		}
	}
	assert(false);
}


Measured memory_bytes: 1024
n = int(input())
l = list(map(int, input().split()))

z = 0
y = []

for i in range(n):
    x = l[i]
    for j in range(max(l)):
        if x % 2 ==0:
            z += 1
            x = int(x/2)
        else:
            y.append(z)
            z = 0
            break

#print(y)
print(min(y))


Measured memory_bytes: 3060
#include<stdio.h>
int main(void){
	int kyo[6],i,j,x;
	for(i=0;i<6;i++){
		scanf("%d",&kyo[i]);
	}
	for(i=0;i<4;i++){
		for(j=i+1;j<4;j++){
			if(kyo[i]<kyo[j]){
				x=kyo[i];
				kyo[i]=kyo[j];
				kyo[j]=x;
			}
		}
	}
	if(kyo[4]<kyo[5]){
		kyo[4]=kyo[5];
	}
	printf("%d\n",kyo[0]+kyo[1]+kyo[2]+kyo[4]);
	return 0;
}

Measured memory_bytes: 600
import java.util.*;

public class Main{
  public static void main(String[]args){
    Scanner sc = new Scanner(System.in);
    int N = Integer.parseInt(sc.nextLine());
    
    int max = 1;
    for(int i = 2; i <= Math.sqrt(N); i++){
      int n = i;
      for(int j = 2; n*i <= N; j++){
        n *= i;
      }
      max = max < n ? n : max;
    }
    System.out.println(max);
  }
}

Measured memory_bytes: 21460
#include <bits/stdc++.h>
using namespace std;
                                                                                   


int main(){
                                                                     

    int n, m, i;

    int g = 0;


    cin >> n;

    vector<int> t(n);

    for( i = 0 ; i < n ; i = i + 1 ){

         cin >> t.at(i);

         g += t.at(i);

         }


    cin >> m;

    vector<int> p(m);

    vector<int> x(m);

    for( i = 0 ; i < m ; i = i + 1 ){

         cin >> p.at(i) >> x.at(i);

         }


    for( i = 0 ; i < m ; i = i + 1 ){

         cout << g - t.at( p.at(i) - 1 ) + x.at(i) << endl;

         }


    return 0;

    }

Measured memory_bytes: 256
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
AB_soretd = sorted(AB, key=lambda a: a[0])
drink_cnt = 0
ans = 0
for i in range(N):
    a = AB_soretd[i][0]
    b = AB_soretd[i][1]
    if M > drink_cnt + b:
        ans += a * b
        drink_cnt += b
    else:
        for i in range(1,b+1):
            if M == drink_cnt + i:
                ans += a * i
                break
        break
print(ans)




Measured memory_bytes: 29268
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef pair<int, int> P;

int n;

int main(){
  cin >> n;
  int sum = 0, cnt = 0;
  while(sum < n){
    cnt++; //?????
    sum += cnt;
    //cerr << sum << endl;
  }
  
  int remove = sum - n;
  for(int i = 1; i <= cnt; i++){
    if(i == remove) continue;
    cout << i << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int binarySearch (vector<int> A, int key, int n){
    int left = 0, right = n, mid;
    while (left < right) {
        mid = (left + right) / 2;
        if (A[mid] == key)  return 1;
        else if (key > A[mid])  left = mid + 1;
        else if (key < A[mid]) right = mid;
    }
    return 0;
}

int main(void){
    int q, k, sum, n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> k;
        if (binarySearch(A, k, n) == 1) sum++;
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 3588
import java.util.Arrays;
import java.util.Scanner;
 
    class Main {
      public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
    int N = sc.nextInt();
    int S[] = new int[N];
    int s = 0;
 
    for(int i = 0; i < N; i++) {
    S[i] = sc.nextInt();
    s += S[i];
    }
    
    if(s % 10 != 0) {
        System.out.println(s);
        return;
    }else {
        Arrays.sort(S);
        for(int i = 0; i < N; i++)
              if(S[i] % 10 != 0) {
                      System.out.println(s -= S[i]);
                      return;
              }
         }
        System.out.println(0);
        return ;
  }
}

Measured memory_bytes: 22996
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
from heapq import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N, M = reads()
edges = [[] for _ in range(N)]
edgesc = defaultdict(lambda: [])
for _ in range(M):
  p, q, c = reads()
  p, q = p-1, q-1
  edges[p].append((q, c))
  edges[q].append((p, c))
  edgesc[p, c].append(q)
  edgesc[q, c].append(p)

INF = 1 << 30
def dijkstra(edges, s):
  result = defaultdict(lambda: INF)
  result[s, -1] = 0
  que = deque([(0, s, -1)])
  while len(que) > 0:
    (d, u, c) = que.popleft()
    if result[u, c] < d:
      continue
    if c < 0:
      for (t, c2) in edges[u]:
        if d + 1 < result[t, c2]:
          result[t, c2] = d + 1
          que.append((d + 1, t, c2))
    else:
      for t in edgesc[u, c]:
        if d < result[t, c]:
          result[t, c] = d
          que.appendleft((d, t, c))
      if d < result[u, -1]:
        result[u, -1] = d
        que.appendleft((d, u, -1))
  return result

dist = dijkstra(edges, 0)
try:
  print(min(d for (u, _), d in dist.items() if u == N-1))
except ValueError:
  print(-1)

Measured memory_bytes: 224116
n = int(input())
c = input()
s = [c[i] for i in range(n)]
for i in range(n-1):

    if len(s) <= i+1:
        break

    while s[i] == s[i+1]:
        del(s[i+1])
        if len(s) <= i+1:
            break


print(len(s))

Measured memory_bytes: 4212
#include<bits/stdc++.h>
using namespace std;

int main(){
    int a,b,c,d,turn;
    cin >> a >> b >> c >> d;
    for(turn = 1; turn <= 220; turn++){
        if(turn % 2 == 1)c -= b;
        if(turn % 2 == 0)a -= d;
        if(a <= 0){
            cout << "No" << endl;
            break;
        } 
        if(c <= 0){
            cout << "Yes" << endl;
            break;
        }
    }
}

Measured memory_bytes: 3620
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#define REP(i,n) for(int i=0;i<(n);++i)
using namespace std;

vector<double> x,y;
int perm[10];

int f(int n){return (n==1)?1:n*f(n-1);}

double g(double i,double j){return sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2));}

int main(){
	int n;
	cin>>n;
	
	x.resize(n);
	y.resize(n);
	REP(i,n) cin>>x[i]>>y[i];
	REP(i,n) perm[i]=i;
	
	double sum=0;
	do{
		REP(i,n-1) sum+=g(perm[i],perm[i+1]);
	}while(next_permutation(perm,perm+n));
	
	double ans=sum/f(n);
	printf("%.10f",ans);
}


Measured memory_bytes: 256
def main():
    MOD = 10**9+7
    N, K = [int(x) for x in input().split()]
    ans = 0
    for k in range(K, N+2):
        ans += k*N - k*(k-1)+1
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9172
num_balls, num_blue, num_red = map(int, input().split())

if num_balls % (num_blue + num_red) <= num_blue:
    print((num_balls // (num_blue + num_red)) * num_blue + num_balls % (num_blue + num_red))
else:
    print((num_balls // (num_blue + num_red))*num_blue + num_blue)


Measured memory_bytes: 38384
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>
#include <string>
#include <time.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }

ll A, B;

int main() {

	scanf("%lld %lld", &A, &B);
	ll G = GCD(A, B);

	set<ll> p;

	p.insert(1);
	for (ll i = 2; i * i <= G; ++i) {
		if (G % i == 0) {
			p.insert(i);
			G /= i;
			i = 1;
		}
	}
	p.insert(G);

	printf("%d\n", p.size());

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,K;
struct Perm{
	int d[100100];
	int& operator[](int x){return d[x];}
	Perm inv()
	{
		Perm tmp;
		for(int i=1;i<=n;++i)tmp.d[d[i]]=i;
		return tmp;
	}
}e;
Perm operator * (Perm a,Perm b)
{
	for(int i=1;i<=n;++i)b[i]=a[b[i]];
	return b;
}
Perm Ppow(Perm x,int k)
{
	Perm r=e;
	while(k)
	{
		if(k&1)r=r*x;
		k>>=1;x=x*x;
	}
	return r;
}
Perm A[11];
int main()
{
	scanf("%d%d",&n,&K);
	for(int i=1;i<=n;++i)e[i]=A[0][i]=i;
	for(int i=1;i<=n;++i)scanf("%d",&A[1][i]);
	for(int i=1;i<=n;++i)scanf("%d",&A[2][i]);
	Perm p=A[1],ip=p.inv(),q=A[2],iq=q.inv();
	Perm s=(((q*ip)*iq)*p),is=s.inv();
	int t=(K-1)/6;
	Perm ans=Ppow(s,t);
	for(int i=3;i<=K-6*t;++i)A[i]=A[i-1]*A[i-2].inv();
//	for(int i=1;i<=n;++i)printf("%d ",ans[i]);puts("");
	ans=ans*A[K-6*t];
//	for(int i=1;i<=n;++i)printf("%d ",ans[i]);puts("");
	ans=ans*Ppow(is,t);
	for(int i=1;i<=n;++i)printf("%d ",ans[i]);puts("");
	return 0;
}


Measured memory_bytes: 13920
#include<algorithm>
#include<iostream>
using namespace std;
int main(){
	int li[1020][12][25] = {};
	int t = 0;
	int y = 0,m = 1,d = 1;
	for(;;t++){
		d++;
		if(m % 2 == 0 && y % 3 != 0){
			if(d == 20){
				d = 1;
				m++;
			}
		}
		else{
			if(d == 21){
				d = 1;
				m++;
			}
		}
		if(m == 11){
			m = 1;
			y++;
		}
		li[y][m][d] = t;
		if(y == 1000 && m == 1 && d == 1)break;
	}
	int n;
	cin>>n;
	while(n--){
		cin>>y>>m>>d;
		cout<<li[1000][1][1] - li[y][m][d]<<endl;
	}
}

Measured memory_bytes: 2364