akhauriyash/Code-Regression huggingface dataset:
/* You are being watched. */


//~ while (clock() <= 69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")

#include <bits/stdc++.h>

//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")

using namespace std;

//~ #include <ext/pb_ds/assoc_container.hpp>
//~ #include <ext/pb_ds/tree_policy.hpp>
//~ using namespace __gnu_pbds;
//~ template <typename T>
//~ using ordered_set =
  //~ tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define all(x) (x).begin(), (x).end()
#define show(x) cerr << __LINE__ << " says: " << #x << " = " << (x) << "\n"
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
//using li = __int128;
//using uli = unsigned __int128;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

double getTime() {
  return clock() / (double) CLOCKS_PER_SEC;
}

void read() {};

template<typename T, typename... Args>
void read(T& a, Args&... args) {
  cin >> a;
  read(args...);
}

void print() {};

template <typename T, typename... Args>
void print(T a, Args... args) {
  cout << a << " \n"[sizeof...(args) == 0];
  print(args...);
}

ll get(ll x) {
  return x * (x + 1) / 2ll;
}

void solve() {
  ll n; cin >> n;
  ll sum = 0;
  for(ll i = 1; i <= n; i++) {
    ll have = (n / i);
    sum += i * get(have);
  }
  print(sum);
}

int main() {
  int t; t = 1;
  while(t--) solve();
}




Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
int n,k,ans,a,b;
string s;
int main()
{
	cin>>n>>k>>s;
	while(a<s.size())
	{
		for(;a<s.size() && s[a]=='1';a++);
		ans=max(ans,a-b);
		for(;a<s.size() && s[a]=='0';a++);
		k--;
		if(k<0)
		{
			for(;b<s.size() && s[b]=='1';b++);
			for(;b<s.size() && s[b]=='0';b++);
		}
		ans=max(ans,a-b);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 512
//https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_c
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}}star;
#define DEBUG if(0)
#endif
#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}
class reverse_range {private:struct I {int x;int operator*() {return x-1;}bool operator!=(I& lhs) {return x>lhs.x;}void operator++() {--x;}};I i, n;public:reverse_range(int n) :i({ 0 }), n({ n }){}reverse_range(int i, int n) :i({ i }), n({ n }){}I& begin() {return n;}I& end() {return i;}};
class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }reverse_range operator!(){return reverse_range(*i,*n);}};

LL A[112345];
LL B[112345];
pair<LL,int> p[112345];
int main(){
    int N;
    cin>>N;
    for(int i:range(N)){
        cin>>A[i]>>B[i];
        p[i]={A[i]+B[i],i};
    }
    sort(p,p+N);
    reverse(p,p+N);
    LL a=0,b=0;
    for(int i:range(N)){
        if(i%2==0)a+=A[p[i].second];
        else b+=B[p[i].second];
    }
    cout<<a-b<<endl;
    return 0;
}

Measured memory_bytes: 3456
#include<cstdio>
#include<cstring>
#include<bits/stdc++.h>
#include<iostream>
#include<math.h>
#include<fstream>
#define sc(x) scanf("%d",&x)
#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORd(i,a,b) for(int i=a;i>b;i--)
#define ff first
#define ss second
#define sz(x) x.size()
#define pb push_back
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);


using namespace std;

typedef pair<int,int> pii;
typedef vector<pii> vii;
const int con = 1e5+7;
static const int INF = 0x3f3f3f3f;
static const int MOD = 1e9+7;


int main() {
    FASTIO;    
    int n,k;cin >> n >> k;
    int arr[n];
    FOR(i,0,n){
        cin >> arr[i];
    }
    
    sort(arr,arr+n);
    
    int ans=INT_MAX;
    for(int i=0,j=k-1;j<n;i++,j++){
        
        ans = min(ans,arr[j]-arr[i]);
    }
    cout << ans;
}

Measured memory_bytes: 640
#include <stdio.h>

int main()
{
    int n,i;
    char s[101];
    scanf("%d %s",&n,s);

    if(n % 2 == 0)
    {
        for (i = 0; i < n / 2; i++)
        {
            if(s[i] != s[i + n / 2])break;
        }
        printf("%s",i == (n / 2) ? "Yes" : "No");
    }
    else
    {
        printf("No");
    }
    
}


Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <string>
#define FI first
#define SE second
#define PF push_front
#define PB push_back
#define PPF pop_front
#define PPB pop_back
#define MA make_pair
#define ll long long
#define PA pair<int,int>
#define VE vector<int>
#define VP vector<PA>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
using namespace std;
//
const int INF=1e9+7;
const int mod=998244353;
//
struct poi{
  int X;int Y;int Z;
  bool operator<(const poi&R)const{
    return X==R.X ? Y==R.Y ? Z<R.Z : Y<R.Y : X<R.X;
  }
};
/*
ll GCD(ll A,ll B){
  return (B==0)?(A):(GCD(B,A%B));
}
//
ll LCM(ll A,ll B){
  return A/GCD(A,B)*B;
}
*/
int main(){
  int X;
  cin>>X;
  int ans=1;
  FOR(i,2,X+1){
    int cnt=i*i;
    if(cnt>X){
      break;
    }
    while(X>=cnt*i){
      cnt*=i;
    }
    ans=max(ans,cnt);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<algorithm>
#include <iostream>
#include <math.h>
#include <cstdio>
#include <string.h>
using namespace std;
int main(void){
	string o,e;
	cin>>o>>e;
	for(int i=0;i<max(o.size(),e.size());i++){
      cout<<o[i];
      if(e[i]>='a'&&e[i]<='z')cout<<e[i];
    }
	cout<<endl;
	return 0;
}


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

int main() {
    int N, M;
    cin >> N >> M;
    int A[N];
    for (int i=0; i<N; i++) cin >> A[i];
    sort(A, A+N, greater<int>());
    int total=0;
    for (int i=0; i<N; i++){
        total+=A[i];
    }
    for (int i=0; i<M; i++){
        if (A[i]<(double)total/(4*M)){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 3572
n,x = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
if a[0] > x:
    b = a[0] - x
    ans = b
    a[0] -= b
for i in range(1,n):
    if a[i-1] + a[i] > x:
        b = a[i-1] + a[i] - x
        ans += b
        a[i] -= b
print(ans)

Measured memory_bytes: 19972
#include <stdio.h>
 
int main() {
  int n, m;
  int o,p;
  int i,j;
 
  scanf("%d %d",&n,&m);
  int t[1000][1000]={0};
  int u[1000]={0}; 
  int v=0;

  for(i = 1; i <= n; i++) {
    for(j = 1; j <= m; j++) {
      scanf("%d",&o);
      t[i][j] = o;
  }}
  for(j = 1; j <= m; j++) {
      scanf("%d",&p);
      u[j]=p;
  }
 
  for(i = 1; i <= n; i++) {
    for(j = 1; j <= m; j++) {
    v += t[i][j] * u[j];
    }
    printf("%d\n", v);
    v = 0;
  }
 
  return 0;
}


Measured memory_bytes: 5764
#include<limits.h>
#include<iostream>
const int STN = INT_MAX;
const int MAX = 520000;
using namespace std;
int L[MAX/2+2], R[MAX/2+2];

int cnt;
void merge(int *A, int left, int mid, int right)
{
	int n1 = mid-left, n2 = right-mid;
	for(int i = 0 ;  i< n1;i++) L[i] = A[left+i];
	for(int i = 0 ; i < n2;i++) R[i] = A[mid+i];
	L[n1] = R[n2] = STN;
	int i = 0 , j = 0;
	for(int k =left; k <right; k++)
	{
		cnt++;
		if(L[i]<=R[j])
			A[k] = L[i++];
		else
			A[k] = R[j++];
	} 	
}
void mergeSort(int *A, int left, int right)
{
	if(left+1<right)
	{	
		int mid = (left + right)/2;
		mergeSort(A, left, mid);
		mergeSort(A, mid, right);
		merge(A,left, mid, right);
	}
}
int main()
{
	int A[MAX];
	cnt =  0;
	int n;
	cin >> n;
	for(int i=0 ; i <n; i++) cin >> A[i];
	
	mergeSort(A, 0, n);
	
	for(int i = 0  ; i <  n ; i++)
		{
	
		if(i) 
			cout << " ";
		 cout <<A[i];
		 }
 	cout <<endl;
 	cout << cnt <<endl;
}

Measured memory_bytes: 6956
#include<stdio.h>
#include<math.h>
int main() {
	int n, A[10000];
	int i, j, ct = 0;
	int flag;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &A[i]);
	}
	for (i = 0; i < n; i++) {
		if (prime(A[i]) == 1)ct++;
	}

	printf("%d\n", ct);
	return 0;
}


	int prime(int x) {
		double sqrtx = sqrt(x);
		if (x < 2) return 0;
		else if (x == 2) return 1;
		else if (x % 2 == 0) return 0; // 偶数はあらかじめ除く

		for (int i = 3; i <= sqrtx; i += 2)
		{
			if (x % i == 0)
			{
				// 素数ではない
				return 0;
			}
		}

		// 素数である
		return 1;
	}



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

int main(void)
{
    int n, x, c=0;
    while(1) {
        cin >> n >> x;
        c = 0;
        int i,j,k;
        if(n==0&&x==0) break;
        for(i=1;i<n-1;i++){
            for(j=i+1;j<n;j++){
                for(k=j+1;k<=n;k++){
                    if(i+j+k==x) c++;
                }
            }
        }
        printf("%d\n", c);
    }
}


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

int main(){
    int a,b;
    string op;
   
    
    while(1){
        cin >> a >> op >> b ;
        if(op=="+"){
            cout << a+b << endl;
        }else if (op=="-"){
            cout << a-b << endl;
        }else if (op=="*"){
            cout << a*b << endl;
        }else if (op=="/"){
            cout << a/b << endl;
        }
        if (op=="?")break;
        
        
    }
    
    return 0;
    
}

Measured memory_bytes: 3088
#include<bits/stdc++.h>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;
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; }


using namespace std;

int main(){
    int K, X;
    cin >> K >> X;
    if (K * 500 >= X) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,k,a[200020],b[200020],ans=0;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[a[i]]++;
	}
sort(a+1,a+1+n);
int m=unique(a+1,a+n+1)-(a+1);
sort(b+1,b+1+n);
for(int i=n-m+1;i<=n-k;++i){
	ans=ans+b[i];
}
cout<<ans;
return 0;
}

Measured memory_bytes: 1920
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int mod = 1000000007;
struct mint{
	ll x;
	mint(ll x = 0):x((x%mod+mod)%mod){}
	mint operator-() const{return mint(-x);}
	mint& operator+=(const mint a){
		if((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a){
		if((x += mod-a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a){
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint a) const{
		mint res(*this);
		return res+=a;
	}
	mint operator-(const mint a) const{
		mint res(*this);
		return res-=a;
	}
	mint operator*(const mint a) const{
		mint res(*this);
		return res*=a;
	}
	mint pow(ll t) const{
		if(!t) return 1;
		mint a = pow(t>>1);
		a *= a;
		if(t&1) a *= *this;
		return a;
	}
	mint inv() const{
		return pow(mod-2);
	}
	mint& operator/=(const mint a){
		return (*this) *= a.inv();
	}
	mint operator/(const mint a) const{
		mint res(*this);
		return res/=a;
	}
	bool operator!=(const mint a){
		return x != a.x;
	}
};

mint dp[105][4][4][2];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    rep(i,4)rep(j,4) dp[2][i][j][0] = 1;
    for(int i = 2; i < n; i++){
        for(int j = 0; j < 4; j++){
            for(int k = 0; k < 4; k++){
                for(int l = 0; l < 4; l++){
                    if(j == 0 && k == 2 && l == 1) continue;
                    if(j == 0 && k == 1 && l == 2) continue;
                    if(j == 2 && k == 0 && l == 1) continue;
                    dp[i+1][k][l][j==0] += dp[i][j][k][0];
                    if((j == 2 || k == 2) && l == 1) continue;
                    dp[i+1][k][l][j==0] += dp[i][j][k][1];
                }
            }
        }
    }
    mint ans = 0;
    rep(i,4)rep(j,4) ans += (dp[n][i][j][0] + dp[n][i][j][1]);
    cout << ans.x << endl;
    return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
Created on Fri Sep 13 22:46:19 2019

"""

S=input()
ODD = S[0::2]
EVEN = S[1::2]

if ("L" not in ODD) and ("R" not in EVEN):
    print('Yes')
else :
    print('No')
     

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;

int main() {
    int N; string s;
    cin>>N>>s;
    for (int i = 0; i < 4; ++i) {
        vector<bool> sheep(N+1,false);
        sheep[0]=(i&10);
        sheep[1]=(i&1);
        for (int i = 2; i <= N; ++i) {

            if(s[i-1]=='o'){
                sheep[i]=!(sheep[i-1]^sheep[i-2]);
            }else{
                sheep[i]=(sheep[i-1]^sheep[i-2]);
            }
        }
        //整合性
        if(sheep[0]==sheep[N] && ((s[0] == 'o')^sheep[0]) == (sheep[1] ^ sheep[N - 1])){
            for (int j = 0; j < N; ++j) {
                cout<<((sheep[j])?"S":"W");
            }
            cout<<endl;
            return 0;
        }
    }
    cout<<-1<<endl;
    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())

signed main() {
    int a, b, c;
    cin >> a >> b >> c;
    if (a + b == c || b + c == a || a + c == b) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <random>
#include <chrono>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
#define INF 1000000000
#define MOD 1000000007


int main(){
    vector<int> V(4);
    vector<int> A = {1, 4, 7, 9};
    for(int &i:V)
        cin >> i;
    sort(V.begin(), V.end());
    if(V==A) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}


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

using namespace std;
using ll =long long;
using db = double;
using vll = vector<long long>;

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; }
#define che(a,string) cout<<"//"<<string <<"=="<<(a)<<"//" <<endl;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define leftunique(a) {SORT(a);(a).erase(unique((a).begin(),(a).end()),(a).end());}
//leftuniqueは配列から同じ要素のものを取り除く 例 4 6 2 1 3 4 1 2 なら 1 2 3 4 6 になる
#define debug(x)  cout << #x << " = " << (x) << endl;
bool IsInt(double a){int b = a/1;if(a==b){return true;}else {return false;}}
bool coY() {cout <<"Yes"<<endl;}
bool coN(){cout <<"No"<<endl;}
const int mod = 1e9 + 7;
const ll INF = 1LL << 60;
//ここから書き始める

vector<int> to[200005];
vector<int> ans;
void dfs(int v, int p = -1){
	for(int u : to[v]){
		if(u == p) continue;
		ans[u] += ans[v];
		dfs(u,v);
	}
}

int main()
{

	int n , q;
	cin >> n >> q;
	rep(i,n-1){
		int a,b;
		cin >> a >> b;
		--a; --b;
		to[a].push_back(b);
		to[b].push_back(a);
	}
	ans.resize(n);
	rep(i,q){
		int p, x;
		cin >> p >> x;
		--p;
		ans[p]+= x;
	}
	dfs(0);
	rep(i,n){
		cout << ans[i] <<endl;
	}
	
}


Measured memory_bytes: 23424
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define int long long

using namespace __gnu_pbds;
using namespace std;

template <class T> using oset = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

void usaco(string name = "")
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(name.size())
    {
        freopen((name+".in").c_str(), "r", stdin);
        freopen((name+".out").c_str(), "w", stdout);
    }
}

int32_t main()
{
    usaco();
    int n, ans = 0;
    cin >> n;
    vector <int> d(n+1, 1);
    for (int i = 2; i <= n; ++i)
        for (int j = i; j <= n; j += i)
            ++d[j];
    for (int i = 1; i <= n; ++i) ans += i*d[i];
    cout << ans << '\n';
}


Measured memory_bytes: 81312
t[9999][9999],j;main(p,W,a,b,c){for(;scanf("%d",&W),W;printf("Case %d:\n%d\n%d\n",p++,t[0][W],j)){for(scanf("%d",&c);c&&scanf("%d,%d",&b,&a);c--)for(j=0;j<=W;j++)t[c-1][j]=(j<a)?t[c][j]:(t[c][j]>t[c][j-a]+b)?t[c][j]:(t[c][j-a]+b);for(j=0;t[0][j]-t[0][W];j++);}} 

Measured memory_bytes: 0
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

constexpr long long MOD = 1000000007;

void calc(const std::vector<std::vector<int>> &edges,
          const std::vector<int> &ans, int i, std::vector<bool> &memo,
          long long &val) {
  memo[i] = true;
  for (auto u : edges[i]) {
    if (!memo[u]) {
      val += std::min(ans[i], ans[u]);
      calc(edges, ans, u, memo, val);
    }
  }
}

int main() {
  int N;
  std::cin >> N;
  std::vector<std::vector<int>> edges(N);
  for (int i = 0; i < N - 1; ++i) {
    int a, b;
    std::cin >> a >> b;
    --a, --b;
    edges[a].push_back(b);
    edges[b].push_back(a);
  }
  std::vector<long long> c(N);
  for (auto &val : c)
    std::cin >> val;
  std::sort(c.begin(), c.end(), std::greater<long long>{});
  std::priority_queue<std::pair<int, int>> q;
  std::vector<int> ans(N, -1);
  {
    auto it =
        std::max_element(edges.begin(), edges.end(),
                         [](auto &x, auto &y) { return x.size() < y.size(); });
    q.push(std::make_pair(it->size(), it - edges.begin()));
  }
  int i = 0;
  while (!q.empty()) {
    auto v = q.top();
    q.pop();
    ans[v.second] = c[i++];
    for (auto e : edges[v.second]) {
      if (ans[e] < 0) {
        int cnt = 0;
        for (auto &u : edges[e]) {
          if (ans[u] < 0)
            ++cnt;
        }
        q.push(std::make_pair(cnt, e));
      }
    }
  }

  long long val = 0;
  std::vector<bool> memo(N, false);
  calc(edges, ans, 0, memo, val);
  std::cout << val << "\n";
  for (int i = 0; i < (int)ans.size() - 1; ++i)
  {
    std::cout << ans[i] << " ";
  }
  std::cout << ans.back() << std::endl;

  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>

using namespace std;

class Fenwick {
public:
	Fenwick(int _N) : N(_N), v(N+1, 0) {}
private:
	int N;
	vector<int> v;
public:
	void add(int val, int p){
		for(int i=p;i<=N;i+=i&-i) v[i] += val;
	}
	int sum(int p){
		int res = 0;
		for(int i=p;i>0;i-=i&-i) res += v[i];
		return res;
	}
};

int main(){
	int N, M; cin >> N >> M;
	Fenwick f(M+1);
	vector< vector<pair<int,int>> > range(M+1);
	for(int i=0;i<N;i++){
		int l, r; cin >> l >> r;
		range[r-l+1].push_back(make_pair(l, r));
	}
	cout << N << endl;
	int all = N;
	for(int i=2;i<=M;i++){
		all -= range[i-1].size();
		for(const pair<int,int>& p : range[i-1]){
			f.add(1, p.first);
			f.add(-1, p.second+1);
		}
		int res = all;
		for(int j=i;j<=M;j+=i) res += f.sum(j);
		cout << res << endl;
	}
}


Measured memory_bytes: 7936
#include<iostream>
#include<string>
using namespace std;

int main()
{
	string str;
	cin >> str;

	int len = str.length();
	int cnt = 0;

	for (int i = 0; i < len/2; i++)
	{
		if (str[i] != str[len - i - 1])cnt++;
	}

	cout << cnt << endl;
	return 0;
}

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

const int MOD = 1e9 + 7;
const int iINF = 1000000000;
const long long int llINF = 1000000000000000000;
const double PI = acos(-1.0);
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;
using ll = long long int;
using P = pair<int, int>;
using edge = struct
{
    int to;
    int cost;
};

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main()
{
    int N, M;
    while (cin >> N >> M && N)
    {
        vector<ll> P(N + 1);
        P[0] = 0;
        rep(i, N) cin >> P[i + 1];

        vector<ll> candi;

        rep(i, N + 1)
        {
            for (int j = i + 1; j <= N; j++)
            {
                candi.push_back(P[i] + P[j]);
            }
        }

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

        ll ans = 0;

        rep(i, candi.size())
        {
            auto itr = upper_bound(candi.begin(), candi.end(), M - candi[i]);

            if(itr == candi.begin()) continue;

            if(M < candi[i] + *(itr - 1)) continue;

            ans = max(ans, candi[i] + *(itr - 1));
        }

        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 10728
#include<cstdio>
 
#define rep(i,n) for(int i=0;i<(n);i++)
 
using namespace std;
 
int main(){
    int n,T,H,L; scanf("%d%d%d%d",&n,&T,&H,&L);
    int t[100],h[100];
    rep(i,n) scanf("%d%d",t+i,h+i);
 
    int yen=0;
    while(1){
        rep(i,n){
            if(t[i]>0){
                t[i]--;
                T++;
                yen+=10;
                if(T>L){ printf("%d\n",i+1); return 0; }
            if(yen==90){
                int back=yen-90;
                if(T<back/10){ printf("%d\n",i+1); return 0; }
                T-=back/10;
                t[i]+=back/10;
                yen=0;
            }
            }
            else if(h[i]>0){
                h[i]--;
                H++;
                yen+=100;
            //if(yen>=90){
                int back=yen-90;
                if(T<back/10){ printf("%d\n",i+1); return 0; }
                T-=back/10;
                t[i]+=back/10;
                yen=0;
            //}
            }
            else{
                printf("%d\n",i+1);
                return 0;
            }
        }
    }
}

Measured memory_bytes: 1032
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<iomanip>
#include<list>
#include<deque>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define END {}
#endif
typedef long long ll;
#define int ll
#define uset unordered_set
#define umap unordered_map
//typedef std::pair<int,int> P;
struct edge{int to,cost;};
const int INF=100000000000000000;
const int INF2=9223372036854775807;
const int MOD=1000000007;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define min(X,Y) (((int)(X)<(int)(Y))?(X):(Y))
#define max(X,Y) (((int)(X)>(int)(Y))?(X):(Y))
#define MAX(X,Y) (*max_element(X,Y))
#define MIN(X,Y) (*min_element(X,Y))
#define NP(X,Y) next_permutation(X,Y)
#define setp(X,Y) cout<<fixed<<setprecision(Y)<<X;
int ceil2(int a,int b){if(a%b==0){return a/b;}else{return a/b+1;}}
int pow2(int a,int b){int r=1;for(int i=1;i<=b;i++){r*=a;}return r;}
int Log2(int a){int t=0;while(1){if(a==0||a==1){break;}a/=2;t++;}return t;}

int N,K;
int R,S,P;
string T;

int A[100010];
int B[100010];
int s[5];
int g[5];
bool F[100010];

signed main(){
	cin>>N>>K>>R>>S>>P>>T;
	REP(i,N){
		if(T[i]=='r'){
			A[i]=0;
		}
		else if(T[i]=='s'){
			A[i]=1;
		}
		else{
			A[i]=2;
		}
	}
	//0=R 1=S 2=P
	s[0]=R;
	s[1]=S;
	s[2]=P;
	g[0]=2;
	g[1]=0;
	g[2]=1;
	int ans=0;
	REP(i,N){
		if(i<K){
			ans+=s[g[A[i]]];
			F[i]=true;
		}
		else{
			if(A[i]!=A[i-K]){
				ans+=s[g[A[i]]];
				F[i]=true;
			}
			else if(F[i-K]==false){
				ans+=s[g[A[i]]];
				F[i]=true;
			}
			else{
				F[i]=false;
			}
		}
		DEB(ans)END
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 1408
#include<stdio.h>



int main(void){

	int x,y,z,d;
	

	scanf("%d %d",&x,&y);

	if(x>=y){	z = x;} 
	else{	z =y;
			y = x;}

	
 
  
  d = z % y;
  while(d!=0){
    z = y;
    y= d;
    d = z % y;
  }


	printf("%d\n",y);

	return 0;
}


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

using namespace std;
#define sf(n) scanf("%d", &n)
#define pd(n) printf("%.12lf", n)
#define pf(n) printf("%d", n)
#define p() printf("\n")
#define ps() printf(" ")
#define ll long long
#define ull unsigned long long
#define MAX 1e9
#define mod 1000 * 1000 * 100 + 7
#define pi 3.1415926536
#define ex 1e18
#define dbl 2e09
#define qu(q) queue<int> q
#define pqu(q) priority_queue<int> q
#define len(s) s.length()
#define sz(x) int(x.size())
#define pb(x) push_back(x)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
int a[50];
int main()
{
    int n, m;
    
    int cnt = 0;
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
    {
        int k;
        cin >> k;
        while (k--)
        {
            int x;
            cin >> x;
            a[x] += 1;
        }
    }
    for (int i = 1; i <= m; ++i)
    {
        if (a[i] == n)
            cnt += 1;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<functional>
#include<cstring>
#include<iostream>
#include<cmath>
#include<queue>
#include<cctype>
#include<string>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define INF 2100000000
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define sec second
#define lb lower_bound
#define ub upper_bound
#define SS stringstream
#define sz(x) ((int)(x).size())
#define SORT(x) sort((x).begin(), (x).end())
#define RSORT(x) sort((x).begin(), (x).end(), greater<int>() )
#define clr(a,b) memset((a),(b),sizeof(a))
int kin[4545],flg[4545454],dp[4545454];	
void sosu()
{
	for(int i=2;i<=1000000;i++) flg[i]=1;
	for(int i=2;i*i<=1000000;i++){
		if(flg[i]==1){
			for(int j=2;j*i<1000000;j++) flg[i*j]=0;
		}
	}
}
int main(void)
{
	sosu();
	int n,x,ff;
	while(cin>>n>>x) {
		if(!n&&!x) break;
		rep(i,0,n) cin>>kin[i];
		rep(i,0,x+1) dp[i]=0;
		dp[0]=1;
		rep(i,0,n) {
			rep(j,0,x) {
				if(dp[j]==1) {
					if(j+kin[i]<=x) dp[j+kin[i]]=1;
				}
			}
		}
		ff=0;
		for(int i=x;i>=2;i--) {
			if(dp[i]&&flg[i]) {cout<<i<<endl,ff=1;break;}
		}
		if(ff==0) cout<<"NA"<<endl;
	}
	return 0;
}
	
	
	
	
	

	

Measured memory_bytes: 10764
#include <iostream>
using namespace std;
typedef long long ll;

const ll MOD = 1000000007;

int a[500005];
ll dp1[2100000];
ll dp2[2100000];
ll s[500005];
ll last[2100000];

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    ll x = 0;
    for(int i = 0; i < 2100000; i++) dp2[i] = 1;
    for(int i = 0; i < n; i++){
        x ^= a[i];
        s[i + 1] = s[i];
        if(x){
            dp2[x] = (dp2[x] + dp1[x] * (s[i + 1] - s[last[x]]) % MOD) % MOD;
            dp1[x] = (dp1[x] + dp2[x]) % MOD;
            last[x] = i + 1;
        }
        else{
            s[i + 1]++;
        }
    }
    ll ans = 0;
    if(x == 0){
        for(int i = 0; i < 2100000; i++) ans = (ans + dp1[i]) % MOD;
        ll c = 0;
        for(int i = 0; i < n; i++){
            x ^= a[i];
            if(x == 0) c++;
        }
        ll k = 1;
        for(int i = 0; i < c - 1; i++) k = k * 2 % MOD;
        ans = (ans + k) % MOD;
    }
    else{
        ans = dp2[x];
    }
    cout << ans << endl;
}


Measured memory_bytes: 43008
package main

import (
	"fmt"
  	"os"
  	"bufio"
  	"strings"
  	"strconv"
)

var sc = bufio.NewScanner(os.Stdin) 

func tran() string{  
  sc.Scan()
  
  return sc.Text()
}

func main(){
  var nm_str = tran()
  slice := strings.Split(nm_str, " ")
  A, _ := strconv.Atoi(slice[0])// A<=20容器サイズ
  B, _ := strconv.Atoi(slice[1]) //B<=A<=20 Aの中身
  C, _ := strconv.Atoi(slice[2]) //c<=20　継ぎ+量
  //fmt.Println(A,B,C)//ここで数字出来ている
  
  lm := B+C//合わせた量
  if A > lm {
    total_size := 0
    fmt.Println(total_size)
  }else if A == lm{
    total_size := 0
    fmt.Println( total_size)
  }else{
    total_size := lm - A
    fmt.Println(total_size)
  }
  
  
  
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fr(i,a,b) for (ll i=(a); i<(b);i++)
#define frr(i,a,b) for(int i=(a-1);i>=(b);i--)
#define vi vector<int>
#define de deque<int>
#define del deque<ll>
#define vl vector<ll>
#define pb push_back
#define ppb pop_back()
#define pf push_front
#define ppf pop_front()
#define mp map<ll,ll>
#define rev(a) reverse(a.begin(),a.end())
#define srt(a) sort(a.begin(),a.end())
#define rsrt(a) sort(a.begin(),a.end(),greater<int>())
#define ln(a) a.length()
#define sz(a) a.size()
int M=1e9+7;

int main()
{ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    //#ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //#endif
 string s,t;
    cin>>s>>t;

    int n,m;
    n=ln(s);m=ln(t);

    int dp[n+1][m+1];
  
    fr(i,0,n+1)fr(j,0,m+1)dp[i][j]=0;

    fr(i,1,n+1)
    if(dp[i][1]!=0 || s[i-1]==t[0])dp[i][1]=1;

    fr(i,1,m)
    if(dp[1][i]!=0 || t[i-1]==s[1])dp[1][i]=1;

    fr(i,1,n+1)
    { 
    fr(j,1,m+1)
    {   
      if(s[i-1]==t[j-1])
      {
        dp[i][j]=dp[i-1][j-1]+1;
      }
    else 
    {
        dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    }
}
}
    
    string ans="";

    //fr(i,0,n+1){fr(j,0,m+1)cout<<dp[i][j]<<" ";cout<<endl;}

     
    while(n>0 && m>0)
    {    //cout<<n<<" "<<m<<endl;
        if(s[n-1]==t[m-1]){ans+=s[n-1];n--;m--;}
        else if(dp[n][m-1]==dp[n-1][m]+1)m--;
        else if(dp[n-1][m]==dp[n][m-1]+1)n--;
        else
        {
            if(n>m)n--;
            else m--;
        }
    }
    rev(ans);cout<<ans;
      return 0;


}


Measured memory_bytes: 35456
import collections
n = int(input())
vs = collections.Counter()
for i in range(n):
  vs[input()] += 1
j = 0
ans = []
for m in vs.most_common():
  if m[1] >= j:
    j = m[1]
    ans.append(m[0])
for a in sorted(ans):
  print(a)

Measured memory_bytes: 43584
#include <iostream>
#include <string>
using namespace std;

int main(){
    int X,A,B;
    cin >> X;
    cin >> A;
    cin >> B;

    int ans=0;
    int count = 0;

    for (int i=0; ans>=0; i++){
        ans = X - (A + i * B); 
        count = i;
    }

    ans = ans + B;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<map>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
char str[100];
map<int,int> mp;
inline int read(){
	int x=0,flag=1;
	char ch=getchar();
	while(!isdigit(ch) && ch!='-')ch=getchar();
	if(ch=='-')flag=-1,ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x*flag;
}
int main(){
	int i,j,k,m,n;
	n=read();
	for(i=1;i<=n;i++){
		int x;
		x=read();
		mp[x]++;
	}
	m=read();
	for(i=1;i<=m;i++){
		int x;
		x=read();
		mp[x]--;
		if(mp[x]<0){
			puts("NO");
			return 0;
		}
	}
	puts("YES");
	return 0;
}

Measured memory_bytes: 9600
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <sstream>
#include <vector>
#include <string>
#include <iomanip>
#include <bitset>
using namespace std;
#define INF	100000000
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define sec second
#define lb lower_bound
#define ub upper_bound
#define SS stringstream
#define rep(i,n) for(int i = 0; i < n; i++)
#define sz(x) ((int)(x).size())
#define SORT(x) sort((x).begin(), (x).end())
#define RSORT(x) sort((x).begin(), (x).end(), greater<int>() )
#define clr(a,b) memset((a),(b),sizeof(a))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<P> Vp;
typedef priority_queue<P, vector<P>, greater<P> > PQ;

int n,m,cnt,t,ans,cnt2;
bool num[1000];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	while(cin >> n >> m){
		if(n == 0 && m == 0) break;
		rep(i,1000) num[i] = false;
		cnt = 0; cnt2 = 0;
		t = 0;
		while(true){
			if(!num[t]){
				cnt++;
				cnt2=0;
				if(cnt%m==0){
					num[t] = true;
					ans = t;
				}
			}
			if(t == n-1) t = -1;
			t++;
			cnt2++;
			if(cnt2 > n+10) break;
		}
		cout << ans+1 << endl;
	}
}

Measured memory_bytes: 1192
//Bokann ga bokka--nn!!
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
char f[1005][1005];
int vis[1005][1005]={};

int main(){
	int h,w,n;
	cin >> h >> w >> n;
	for(int i=0;i<h;i++)
	{
		scanf("%s",f[i]);
	}
	P za[10];
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			if(f[i][j]=='S')
			{
				za[0]=mp(i,j);
			}
			if(f[i][j]-'0'>=1 && f[i][j]-'0'<=9)
			{
				za[f[i][j]-'0']=mp(i,j);
			}
		}
	}
	int ret=0;
	for(int i=0;i<n;i++)
	{
		queue<P1>que;
		que.push(mp(za[i],0));
		memset(vis,0,sizeof(vis));
		while(1)
		{
			P1 p=que.front(); que.pop();
			int x=p.first.first;
			int y=p.first.second;
			int z=p.second;
			if(p.first==za[i+1]) { ret+=z; break;}
			if(vis[x][y]) continue;
			vis[x][y]=true;
			int dx[4]={1,0,-1,0};
			int dy[4]={0,1,0,-1};
			for(int j=0;j<4;j++)
			{
				if(0<=x+dx[j] && x+dx[j]<h && 0<=y+dy[j] && y+dy[j]<w && f[x+dx[j]][y+dy[j]]!='X')
				{
					que.push(mp(mp(x+dx[j],y+dy[j]),z+1));
				}
			}
			
		}
	}
	cout << ret << endl;
}

Measured memory_bytes: 6176
main = do
    [n,h,w] <- ((fmap read . words) <$> getLine) :: IO [Int]
    res <- solve n 0 h w
    print res

solve :: Int -> Int -> Int -> Int -> IO Int
solve 0   ac _ _ = return ac
solve cnt ac h w = do
    [a,b] <- ((fmap read . words) <$> getLine) :: IO [Int]
    case a>=h && b>=w of
        True -> solve (cnt-1) (ac+1) h w
        otherwise -> solve (cnt-1) ac h w


Measured memory_bytes: 1020
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
    private static final int MAX = (int) 1e5 + 1;

    public static void main(final String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int q = scanner.nextInt();
        final int[] like2017 = new int[MAX];
        final Set<Integer> primeNumbers = sieveOfEratosthenes(MAX);

        for (int i = 1; i < MAX; i++) {
            like2017[i] = isLike2017(i, primeNumbers) ? like2017[i - 1] + 1 : like2017[i - 1];
        }

        for (int i = 0; i < q; i++) {
            final int begin = scanner.nextInt();
            final int end = scanner.nextInt();
            System.out.println(like2017[end] - like2017[begin - 1]);
        }
    }

    private static boolean isLike2017(final int number, final Set<Integer> primeNumbers) {
        return number % 2 == 1 && primeNumbers.contains(number) && primeNumbers.contains((number + 1) / 2);
    }

    private static Set<Integer> sieveOfEratosthenes(final int number) {
        List<Integer> numbers = IntStream.rangeClosed(2, number)
                .boxed()
                .collect(Collectors.toList());

        final int sqrt = (int) Math.sqrt(number);
        final Set<Integer> primeNumbers = new HashSet<>();
        int condition;

        do {
            final int prime = numbers.get(0);
            primeNumbers.add(prime);
            numbers = numbers.stream()
                    .filter(i -> i % prime != 0)
                    .collect(Collectors.toList());
            condition = prime;
        } while (condition < sqrt);

        primeNumbers.addAll(numbers);
        return primeNumbers;
    }
}


Measured memory_bytes: 94700
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) rep(i, x.size()) cerr << x[i] << (i == x.size() - 1 ? "\n" : " ")
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
const int INF = ((1LL << 30) + (1LL << 29));
const int MOD = 1000000007;

//=============================

int N;
vector<int> A;

void input()
{
    cin >> N;
    A.resize(N);
    rep(i, N)
    {
        cin >> A[i];
    }
}
//=========FUNCTIONS==========

void solve()
{
    int ans = 0;
    for (auto x : A){
        ans += (x-1);
    }

    cout<<ans<<endl;

}

//=============================
signed main()
{
    input();
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N];
int main()
{
    int n;
    cin>>n;
    int cnt4=0,cnt2=0;
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
        a[i]%=4;
        if(a[i]==0)
            cnt4++;
        else if(a[i]==2)
            cnt2++;
    }
    int cnt=n-cnt2-cnt4;
    if(cnt2)
    {
        if(cnt4>=cnt){
            cout<<"Yes";
            return 0;
        }
    }
    else
    {
        if(cnt4&&(cnt4+1>=cnt)){
            cout<<"Yes";
            return 0;
        }
    }
    cout<<"No";
    return 0;
}


Measured memory_bytes: 640
/******************************************************************************

            EYENINE,THE ELDER_WAND!!!
            THE ROOT OVER MINUS EIGHTY ONE!!

*******************************************************************************/

#include<bits/stdc++.h>
#define ALL_UP_WITH return 0
#define vi vector<int>
using namespace std;
int count1=0;
int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    string s;
    cin>>n>>s;
    int count1=0;
    for(int i=0;i<n;i++){
        if(s[i]!=s[i+1]){
            count1++;
        }

    }
    cout<<count1<<endl;

    ALL_UP_WITH;
}


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

int main(){
    string s; cin >> s;
    string t; cin >> t;
    int a; cin >> a;
    int b; cin >> b;
    string u; cin >> u;

    if (s==u) {
        a=a-1;
    }else{
        b=b-1;
    }
    cout << a << " " << b << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int h,n,sum,w[N],c[N],f[N][10010];
int main(){
	cin>>h>>n;
	for(int i=1;i<=n;i++)
		scanf("%d%d",&w[i],&c[i]);
	for(int i=1;i<=h;i++)
		f[0][i]=199999999;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=h;j++){
			f[i][j]=min(f[i-1][j],f[i][max(0,j-w[i])]+c[i]);
		}
	printf("%d\n",f[n][h]);
	return 0;
}

Measured memory_bytes: 39424
#pragma GCC optimize("Ofast","inline")
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"---------------"#x"---------------"<<endl
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
						For(_x,L,R)cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef vector <int> vi;
LL read(){
	LL x=0,f=0;
	char ch=getchar();
	while (!isdigit(ch))
		f|=ch=='-',ch=getchar();
	while (isdigit(ch))
		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int N=100;
int n;
int x[N],y[N];
map <pair <int,int>,int> a;
int main(){
	n=read();
	For(i,1,n)
		x[i]=read(),y[i]=read();
	For(i,1,n)
		For(j,1,n)
			if (i!=j)
				a[mp(x[i]-x[j],y[i]-y[j])]++;
	int mx=0;
	For(i,1,n)
		For(j,1,n)
			if (i!=j)
				mx=max(mx,a[mp(x[i]-x[j],y[i]-y[j])]);
	cout<<n-mx;
	return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        k--;
    //    int f[] = new int[k];
   String s = sc.next();
         
       char c[] = s.toCharArray();
      s = s.toLowerCase();
     char d []  = s.toCharArray();
       
        for(int i=0 ; i<n ; i++){
       if(i==k)
       {
           c[i] = d[k];
           break ;
       }
        
    }   for(int i = 0 ; i <c.length ; i++)
        System.out.print(c[i]);
} 
}


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

const int N = (int)2e5 + 5;

ll t[2], a[2], b[2], tt;

void init() {
  cin >> t[0] >> t[1] >> a[0] >> a[1] >> b[0] >> b[1];
  tt = t[0] + t[1];
}
void solve() {
  ll pa0 = t[0] * a[0], pb0 = t[0] * b[0], pa1 = pa0 + t[1] * a[1], pb1 = pb0 + t[1] * b[1];
//cerr << pa0 << ' ' << pb0 << ' ' << pa1 << ' ' << pb1 << '\n';
  assert(pa0 != pb0);
  if(pa1 == pb1) cout << "infinity\n";
  else if(pa1 > pb1) {
    if(pa0 > pb0) cout << "0\n";
    else cout << (pb0 - pa0) / (pa1 - pb1) * 2 + ((pb0 - pa0) % (pa1 - pb1) != 0) << '\n';
  }
  else if(pa1 < pb1) {
    if(pa0 < pb0) cout << "0\n";
    else cout << (pa0 - pb0) / (pb1 - pa1) * 2 + ((pa0 - pb0) % (pb1 - pa1) != 0) << '\n';
  }
}

int main() {
  init();
  solve();
}


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

int main() {
  int a,b,c;
  long long int k;
  cin >> a >> b >> c >> k;
  if(k%2==0){
    if(a-b>pow(10,18)){
      cout << "Unfair" << endl;
    }
    else cout << a-b << endl;
  }
  else{
    if(b-a>pow(10,18)){
      cout << "Unfair" << endl;
    }
    else cout << b-a << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
  int n;
  cin>>n;
  char a[n];
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
  }
  int p1=0,p2=n-1,num=0;
  while(p2>p1)
  {
    while(a[p1]=='R')
    {
      p1++;
      if(p1==n)
        break;
    }
    while(a[p2]=='W')
    {
      p2--;
      if(p2==-1)
        break;
    }
    if(p2>p1)
    	num++;
    p1++;
    p2--;
  }
  cout<<num<<endl;
  return 0;
}

Measured memory_bytes: 3352
#include <iostream>
#include <limits>
#include <cmath>
using namespace std;

struct Point2D {
    float x, y;

    Point2D() {}
    Point2D(float ax, float ay) {
        x = ax;
        y = ay;
    }
    Point2D operator -(const Point2D &p) const {
        return Point2D(x - p.x, y - p.y);
    }
    double distance(const Point2D &p) const {
        return sqrt(pow(x - p.x, 2) + pow(y - p.y, 2));
    }
    double slope(Point2D &p) {
        return (p.x != x) ? (p.y - y) / (p.x - x) : numeric_limits<float>::infinity();
    }
    double cross(Point2D &p) { // only z
        return x * p.y - y * p.x;
    }
};

istream &operator>>(istream &is, Point2D &p) {
    is >> p.x >> p.y;
    return is;
}

ostream &operator<<(ostream &os, Point2D &p) {
    os << fixed << p.x << " " << p.y;
    return os;
}

int circles_intersection(double distance, double ra, double rb)
{
    if (distance > ra + rb)
        return 0;
    else if (distance >= abs(ra - rb))
        return 1;
    else if (ra > rb)
        return 2;
    else
        return -2;
}

int main()
{
    Point2D pa, pb;
    double ra, rb;

    int n;
    cin >> n;

    for (;n-- && cin >> pa >> ra >> pb >> rb;)
        cout << circles_intersection(pa.distance(pb), ra, rb) << endl;

    return 0;
}

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

int main(){
  long long X,K,D;
  cin >> X >> K >> D;
  
  if (X<0){
    X=-X;
  }
  
  long long ans=X;
  if (X/D>K){
    ans=X-K*D;
  }
  else{
    if ((X/D)%2 == K%2){
      ans=X%D;
    }
    else{
      ans=D-X%D;
    }
    
  }
  
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 3164
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define rep(n) for(int i=0;i<n;i+=1)
#define prarr(a,n) rep(n) cout<<a[i]<<endl printf("%s\n"," " );
#define sc(a) scanf("%d",&a);
#define scl(a) scanf("%lld",&a);
#define scf(a) ascanf("%f",&a);
#define fi first
#define se second
#define pu push_back
#define inf 1000000001
#define MOD 1000000007 
#define INF 100000000000001
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,x;
    int a[200];
    cin>>n>>m>>x;
    int l = 0;
    int r= 0;
    rep(m) 
    {
	    cin>>a[i];
	    if(a[i]<x) l++;
	    if(a[i]>x) r++;
    }
    cout<<min({l,r})<<endl;
    return 0;

}
    

Measured memory_bytes: 256
# ITP1_7_B
r, c = map(int, input().split())
columns = [[0 for i in range(c+1)] for j in range(r+1)]

# 入力文字列を取得
for i in range(r):
    columns[i] = list(map(int, input().split()))

# 行の合計を各列のお尻につける
for i in range(r):
    s = sum(columns[i])
    columns[i].append(s)

# 列の合計をつくって一番下につくる
for j in range(c):
    s = 0
    for i in range(r):
        s += columns[i][j]
    columns[r][j] = s

# 行の合計の合計    
columns[r][c] = (sum(columns[r]))

# すべてを表示
for i in range(r+1):
    for j in range(c+1):
        if j == c:
            print(str(columns[i][j]))
        else:
            print(str(columns[i][j]) + " ", end="")


Measured memory_bytes: 6216
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>

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

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;}

int main(){
  int n; cin >> n;
  string s; cin >> s;

  vector<int> R, G, B;
  rep(i, n){
    if (s[i] == 'R') R.push_back(i);
    else if (s[i] == 'G') G.push_back(i);
    else B.push_back(i);
  }

  ll ans = R.size() * G.size() * B.size();
  for (int i = 0; i < n; ++i){
    for (int j = i + 1; j < n; ++j){
      if (s[i] == s[j]) continue;
      int k = 2 * j - i;
      if (n <= k) break;
      if (s[i] != s[k] && s[j] != s[k]) --ans;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3660
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int r = sc.nextInt();
		
		int rate = n >= 10 ? r : r + 100 * (10 - n);
		System.out.println(rate);
		
		sc.close();
	}
}






Measured memory_bytes: 21972
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
using ll = long long;
using graph = std::vector<std::vector<ll>>;

using namespace std;

int main() {
    int N;
    cin >> N;
    string S,T;
    cin >> S>> T;
    for(int i = 0; i < N; i++){
        cout << S[i];
        cout << T[i];
    }
    cout << endl;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    A = list(map(int,input().split()))
    
    ans = 0
    for i in range(N):
        for j in range(N-i-1):
            ans += A[i]*A[i+j+1]
            
    print(ans)
        
if __name__ == "__main__":
    main()

Measured memory_bytes: 3060