akhauriyash/Code-Regression huggingface dataset:
/*
гонфлад
*/
#pragma ARCENIY_KIRILLOV_UVIDEL_KROKODILOV
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC push_options
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC pop_options
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define rng(a) a.begin(), a.end()
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;



main(){
    int n;
    cin >> n;
    vector <int> a(n);
    map <int,int> b;
    for (int i = 0; i < n; i++){
        cin >> a[i];
        b[a[i]]++;
    }
    if (b.size() > 3){
        cout << "No";
        return 0;
    }
    if (b.size() == 3){
        vector<pair<int,int> > c;
        for (auto x : b)
            c.pb(x);
        if ( (c[0].fi ^ c[1].fi) == c[2].fi){
            if (c[0].se == c[1].se && c[1].se == c[2].se){
                cout << "Yes";
                return 0;
            }
        }
        cout << "No";
        return 0;
    }
    if(b.size() == 1){
            int c;
            for (auto x : b)
                c = x.fi;
            if (c == 0){
                cout << "Yes";
            }else cout << "No";
            return 0;
    }
    int c = -1;
    int d = -1;
    int t = -1;
    for (auto x : b){
        if (d == -1){
            d = x.se;
            t = x.fi;
        }else{
            c = x.se;
            t = min(t, x.fi);
            }
    }
    if (t != 0){
        cout << "No";
        return 0;
    }
    if (d + d == c){
        cout << "Yes";
        return 0;
    }
    cout << "No";

}


Measured memory_bytes: 4224
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>
#include <bitset>
#include <time.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = (1LL << 31) - 1;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1
#define MAX_N 100100 * 3

int M, T, PP, R;
bool table[50][10];
int sum[50][10];

bool is(const pair<P, int> p1, const pair<P, int> p2) {
	if (p1.first.first == p2.first.first) {
		if (p1.first.second == p2.first.second) {
			return p1.second > p2.second;
		}
		return p1.first.second < p2.first.second;
	}
	return p1.first.first > p2.first.first;
}

int main() {
	while (cin >> M >> T >> PP >> R&&M + T + PP + R) {
		rep(i, 50)rep(j, 10) {
			table[i][j] = 0;
			sum[i][j] = 0;
		}
		vector<pair<P, int>> vpi;
		rep(i, R) {
			int m, t, p, j;
			cin >> m >> t >> p >> j;
			t--; p--;
			if (j == 0) {
				table[t][p] = 1;
				sum[t][p] += m;
			}
			else sum[t][p] += 20;
		}
		rep(i, T) {
			int a = 0, t = 0;
			rep(j, PP) {
				if (table[i][j]) {
					a++;
					t += sum[i][j];
				}
			}
			vpi.push_back({ {a,t},i + 1 });
		}
		sort(ALL(vpi), is);
		/*rep(i, T) {
			cout << "!!" << vpi[i].first.first << " " << vpi[i].first.second << " " << vpi[i].second << endl;
		}*/
		cout << vpi[0].second;
		rep(i, T - 1) {
			if (vpi[i + 1].first.first == vpi[i].first.first&&
				vpi[i + 1].first.second == vpi[i].first.second) {
				cout << "=" << vpi[i + 1].second;
			}
			else {
				cout << "," << vpi[i + 1].second;
			}
		}
		cout << endl;
	}
}

Measured memory_bytes: 3052
import math
X = int(input())

#(t-1)(t-2)//2 < X <= t(t-1)//2 を満たすtを求める
t = int(math.sqrt(2*X))
while True:
    if t*(t-1) < 2*X:
        t += 1
    else:
        break

print(t-1)

Measured memory_bytes: 3060
#include<iostream>
#include <cmath>
#include <iomanip>
#include <cstdlib>

using namespace std;

int main()
{
  int n;
  int x[100];
  int y[100];
  int i;
  long double p1=0.0;
  long double p2=0.0;
  long double p3=0.0;
  long double p=0.0;
  int max=0;
  
  cin >>n;
  
  for(i=0;i<n;i++)
    cin >>x[i];
  for(i=0;i<n;i++)
    cin >>y[i];
  
  for(i=0;i<n;i++)
    p1=p1+abs(x[i]-y[i]);
  
  for(i=0;i<n;i++)
  {
    p2+=abs(x[i]-y[i])*abs(x[i]-y[i]);
  }
  p2=sqrt(p2);
  
  for(i=0;i<n;i++)
  {
    p3+=abs(x[i]-y[i])*abs(x[i]-y[i])*abs(x[i]-y[i]);
  }
  p3=pow(p3, 1.0/3.0);
  
  for(i=0;i<n;i++)
  {
    if(abs(x[i]-y[i])>max)
      max=abs(x[i]-y[i]);
  }
  p=max;
  
  cout << fixed << setprecision(6) << p1 << "\n";
  cout << fixed << setprecision(6) << p2 << "\n";
  cout << fixed << setprecision(6) << p3 << "\n";
  cout << fixed << setprecision(6) << p << "\n";
  
}

Measured memory_bytes: 1272
N = int(input())
S = str(input())
cnt = 0

ans = []
for i in range(0,N):
  if S[i] == "I":
    cnt = cnt+1
  elif S[i] == "D":
    cnt = cnt-1
  ans.append(cnt)

if max(ans) <= 0:
  print("0")
else:
  print(max(ans))

Measured memory_bytes: 3060
#KNOT PUZZLE
N,L=map(int,input().split())
lists=list(map(int,input().split()))
flag=False
J=0
for i in range(N-1):
    if lists[i]+lists[i+1]>=L:
        J=i+1
        flag=True
        break
if not flag:
    print("Impossible")
if flag:
    print("Possible")
    for i in range(100001,0,-1):
      if 1<=J-i<=N-1:
        print(J-i)
      if 1<=J+i<=N-1:
        print(J+i)
    print(J)
      
    




    



Measured memory_bytes: 14052
#include <stdio.h>
#include <string.h>


int main()
{
	char arr[20];
	int i;
	for(i = 0; i < 20; i++){
		arr[i] = '\0';
	}
	scanf("%s",arr);
	for(i = 0; i < 20; i++){
		if(arr[19-i] != '\0'){
			printf("%c",arr[19-i]);
		}
	}printf("\n");
	return 0;
}

Measured memory_bytes: 524
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define repr(e,x) for(auto& e:x)
using namespace std;
typedef long long ll;
typedef long double ld;
//typedef pair<int,int> P;
int const INF=1001001001;
ll const LINF=1001001001001001001;
ll const MOD=1000000007;

ll N;
ll a[100000];

int main(){
    cin>>N;
    rep(i,N) cin>>a[i];

    map<ll,ll> m;
    rep(i,N) m[a[i]]++;

    ll ans=0;
    repr(e,m){
        if(e.first>e.second) ans+=e.second;
        else ans+=e.second-e.first;
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 10356
# 解説AC
# https://black-thunder.hatenablog.com/entry/20200610/1591774050
# 基底の最上位bitの位置はそれぞれ異なる
# https://betrue12.hateblo.jp/entry/2019/03/18/005750

m = (10**18).bit_length()
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    s = list(map(int, input()))
    base = [0]*m
    for i in reversed(range(n)):
        for j in reversed(range(m)):
            if (1<<j)&a[i]:
                if base[j] == 0:
                    if s[i]:
                        print("1")
                        return
                    else:
                        base[j] = a[i]
                    break
                a[i] ^= base[j]
    print("0")

t = int(input())
for i in range(t):
    solve()

Measured memory_bytes: 68664
//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define pb push_back
#define in insert
#define er erase
#define ct count
#define ep empty
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define _rfor(i,a,b) for(int i = (a);i>(b);--i)
#define _sfor(p,st) for(auto &p:st)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
const double eps = 1e-6;
const double pi = acos(-1.0);
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
ll qpow(ll x, ll y) { ll ans = 1; for (; y > 0; y >>= 1) { if (y & 1)ans *= x; x *= x; }return ans; }
ll qpow(ll x, ll y, int MOD) { ll ans = 1; for (; y > 0; y >>= 1) { if (y & 1)ans = ans*x%MOD; x = x*x%MOD; }return ans; }
void exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){x=1;y=0;return;}
    exgcd(b,a%b,x,y);
    ll X=x;
    x=y; y=X-a/b*y;
}
ll inv(ll x, int mod = MOD) { return qpow(x, mod - 2) % mod; }
ll m_m(ll a){ return (a%MOD+MOD)%MOD; }

string s[10];
int main() {
	//ofstream cout("E:\\acm dream\\out.txt",ios::out);
	FIO;
    #ifdef err
	double be = clock();
    #endif
    int n,m,k;cin>>n>>m>>k;
    vector<int>r,c;
    _for(i,0,n)cin>>s[i];
    int ans = 0;
    int cnt = 0;
    _for(i,0,n){
        _for(j,0,m)cnt+=(s[i][j]=='#');
    }
    _for(i,0,1<<n){
        int res = cnt;
        _for(j,0,n){
            if((1<<j)&i){
                r.pb(j);
                _for(l,0,m)res-=(s[j][l]=='#');
            }
        }
        _for(j,0,1<<m){
            int res1 = res;
            _for(l,0,m){
                if((1<<l)&j){
                    c.pb(l);
                    _for(q,0,n)res1-=(s[q][l]=='#');
                }
            }
            _sfor(x,r){
                _sfor(y,c){
                    if(s[x][y]=='#')res1++;
                }
            }
            
            if(res1==k)++ans;
            c.clear();
        }
        r.clear();
    }
    cout<<ans;
    #ifdef err
	double en = clock();
    cout<<"time: "<<fixed<<setprecision(8)<<en-be;
    #endif
	return 0;
}

Measured memory_bytes: 3608
n, k = map(int, input().split())
d = []
a = []
for i in range(k):
    d.append(int(input()))
    a.append(list(map(int, input().split())))

aa = [0]*n

for j in a:
    for t in j:
        aa[t - 1] += 1

ans = 0

for z in aa:
    if z == 0:
        ans += 1
    else:
        ans += 0

print(ans)

Measured memory_bytes: 9168
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <math.h>
#include <memory>
#include <cctype>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <cstdlib>
#include <random>
#include <chrono>
#include<iterator>
#include <locale>

#define debug(a) cerr << #a << " = " << a << endl;
/*,---.   ,--.                         ,--.
'   .-'  |  ,---.  ,--.,--. ,--.  ,--. `--'
`.  `-.  |  .-.  | |  ||  |  \  `'  /  ,--.
.-'    | |  | |  | '  ''  '   \    /   |  |
`-----'  `--' `--'  `----'     `--'    `--'*/
using namespace std;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    map<int, int> have;
    vector<int> val(n);
    for(int i = 0;i<n;i++){
        cin >> val[i];
        have[val[i]]++;
    }
    if(val[0] != 0 || have[0] > 1){
        cout<<0;
        return 0;
    }
    long long res = 1;
    int cnt = 1;
    for(int i = 1;i<=n;i++){
        if(have[i] == 0){
            if(cnt != n){
                res = 0;
            }
            break;
        }else{
            for(int j = 0;j<have[i];j++){
                res*=have[i-1];
                res%=998244353;
            }
            cnt+=have[i];
        }
    }
    cout<<res;
}

Measured memory_bytes: 7764
loop{
	n,k = gets.split.map(&:to_i)
	if n == 0 and k == 0 then
		break
	end
	s = gets.split.map(&:to_i)
	
	n.times do
		s = gets.split.each_with_index.map{|b,i| (s[i] - b.to_i())}
	end
	
	print s.all?{|a| a >= 0} ? "Yes" : "No"
	print "\n"
}

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

int main() {
  int n,x,t; cin >> n >> x >> t;
  
  int times = n / x;
  if(n % x != 0) times++;
  
  int ans = times * t;
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
int main(void){
    long long N;
    cin >> N;
    std::vector<long long> A(N);
    std::vector<long long> B(N);
    for(long long i=0;i<N;i++){
        cin >> A.at(i);
    }
    sort(A.begin(),A.end());
    reverse(A.begin(),A.end());
    
    long long sum=0;
    
    long long tmp=A.at(0);
    long long after=1;
    long long j=0;
    // int low=0;
    for(int i=0;i<N;i++){
        // cout<<"i:"<<i<<" sum:"<<sum<<endl;
        if(A.at(i)!=tmp){
            sum += tmp * i;
            // cout<<sum<<endl;
            sum -= (min(after,N)-i) * (A.at(i-1));
            // cout<<sum<<endl;
            after=i*2;
            if(after>N){
                sum-=(after-N)*A.at(i-1);
                j=1;
            }
            // cout<<sum<<endl;
            tmp=A.at(i);
        }
        
        if(i+1==N && j==0){
            sum+=A.at(i)*(N-after);
        }
    }
    
    cout << sum <<endl;
    // for(int i=0;i<N;i++){
    //     cout << A.at(i)<<endl;
    // }
    
}

Measured memory_bytes: 6428
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)
#define pcnt __builtin_popcountll
#define rng(a) a.begin(), a.end()
#define sz(x) (int)(x).size()
#define v(T) vector<T>
#define vv(T) v(v(T))
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;

template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
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; }

ll INF = 1001001001;
ll LINF = 1001001001001001001ll;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n;
    cin>>n;
    vector<string> ss(n);
    cin>>ss;

    ll ans = 0;
    ll acnt = 0;
    ll bcnt = 0;
    ll abcnt = 0;
    rep(i, n) {
        int m = sz(ss[i]);
        rep(j, m - 1) {
            if (ss[i][j] == 'A' && ss[i][j + 1] == 'B') ans++;
        }
        if (ss[i][0] == 'B' && ss[i].back() == 'A') abcnt++;
        else if (ss[i][0] == 'B') bcnt++;
        else if (ss[i].back() == 'A') acnt++;
    }
    ans += max(abcnt - 1, 0ll);
    abcnt = abcnt > 0;
    if (abcnt <= min(acnt, bcnt)) {
        ans += abcnt * 2;
        acnt -= abcnt;
        bcnt -= abcnt;
        ans += min(acnt, bcnt);
    }
    else {
        if (acnt == 0) ans += min(abcnt, bcnt);
        else ans += min(abcnt, acnt);
    }
    cout<<ans<<endl;
}

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

// int/long:		-2,147,483,648 - 2,147,483,648 (-2^31 <= int < 2^31)
// long/long long:	-9,223,372,036,854,775,808 - 9,223,372,036,854,775,807 (-2^63 <= long < 2^63)

#define	INF (1<<29)
//536,870,912

// lower_bound(A.begin(), A.end(), N)
// upper_bound(...

// A.erase(unique(A.begin(), A.end()), A.end())

// bit: &/and, |/or, ^/xor, ~/not

// getline(cin, String)

// Graph
// Warshall-Floyd: Distance between each node, N^3
// Dijkstra: Distance from the start node, N^2
// DFS(Depth-First Search)

#define	MOD 1000000007

int	main() {
	int R, G, B, N;
	cin >>R >>G >>B >>N;
	long S=0;
	int NN=N;
	while(NN>=0) {
		int NNN=NN;
		while(NNN>=0) {
			if (0==NNN%B)
				S++;
			NNN -=G;
		}
		NN -=R;
	}
	cout <<S <<endl;
	return 0;
}



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

using namespace std;

typedef long long ll;

#define MOD (int)1e9+7
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>b;--i)
#define vi vector<int>
#define vl vector<ll>
#define ld long double
#define vvi vector<vector<int>>
#define vvl vector<vector<long long>>
#define pii pair<int,int>
#define pll pair<long,long>
#define vpii vector<pii>
#define vpll vector<pll>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define PI 3.1415926535897932384626433832795
#define fix(f,n) fixed<<setprecision(n)<<f
#define all(x) x.begin(),x.end()
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);



ll powM(ll a,ll b,ll m )
{ 
  a%=m;
  ll ans=1;
  while(b>0)
  {
    if(b&1)ans=ans*a%m;
    a=a*a%m;
    b>>=1;
  }

return ans;
}

ll pow(ll a,ll b)
{ 
  
  ll ans=1;
  while(b)
  {
    if(b&1)ans=ans*a;
    a=a*a;
    b>>=1;
  }

return ans;
}

ll dp[105][1005];
char ch[105][1005];


int main()
{fast


ll n;cin>>n;

string s,t;
cin>>s>>t;

ll ans=0;


for(ll i=0;i<n;i++)
{
string t1=t.substr(0,i+1);
string s1=s.substr(n-i-1,i+1);
if(s1==t1)
{
  ans=max(ans,i+1);
}
}


cout<<2*n-ans<<"\n";


 return 0;

}


Measured memory_bytes: 256
#N=gets.to_i
#S=gets.chomp
#A=(0...N).map{gets.to_i}
#sum=A.inject(&:+)
#B=gets.split.map(&:to_i)
 
 
N,M=gets.split.map(&:to_i)
LRs=(0...M).map{gets.split.map(&:to_i)}
 
lmax=-1
rmin=N+1
LRs.each do |l,r|
  lmax=[l,lmax].max
  rmin=[r,rmin].min
end
if rmin<lmax
  p 0
else
  p rmin-lmax+1
end

Measured memory_bytes: 9596
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)
int main() {
    int x, a, b;
    cin >> x >> a >> b;
    if ( abs(x-a) > abs(x-b) ) cout << "B" << endl;
    else                       cout << "A" << endl;
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T>& V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> >& Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T>& mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }
template<typename T>vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t,const V &v){t=v;}
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t,const V &v){for(auto &e:t) fill_v(e,v);}
/*
 <url:https://atcoder.jp/contests/abc145/tasks/abc145_c>
 問題文============================================================
 C - Average Length
 =================================================================
 解説=============================================================
 
 ================================================================
 */

template<class Type>
Type solve(Type res = Type()){
    using Point = complex<double>;
    int N; cin >> N;
    vector<Point> ps(N);
    for(int i = 0; i < N;i++){
        double x,y; cin >> x >> y;
        ps[i] = Point(x,y);
    }
    double sum = 0;
    vector<int> order(N);
    iota(order.begin(),order.end(),0);
    do{
        for(int i = 1; i < N;i++){
            sum += abs(ps[order[i]]-ps[order[i-1]]);
        }
    }while(next_permutation(order.begin(),order.end()));
    double p = 1;
    for(int i = 1; i <= N;i++){
        p *= i;
    }
    res = sum/p;
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    // solve(0);
    cout << fixed << setprecision(15) << solve<double>() << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int Y = sc.nextInt();
    for (int i = 0; i <= N  && i*10000 <= Y; i++) {
      for (int j = 0; i+j <= N && i*10000 + j*5000 <= Y; j++) {
        int remain = Y - (i*10000 + j*5000);
        if (remain / 1000 == N - (i+j)) {
          System.out.println(i + " " + j + " " + remain / 1000);
          return;
        }
      }
    }
    System.out.println("-1 -1 -1");
  }
}

Measured memory_bytes: 21972
//   //  /////       ///      
//  //   //  //     // //     
// //    //   //   //   //    
////     //   //  //     //   
// //    //   //  /////////    
//  //   //  //   //     //    
//   //  /////    //     //    

#include <bits/stdc++.h>
using namespace std;
#define forstl(i,v) for(auto &i: v)
#define forn(i,e) for(int i = 0; i < e; i++)
#define forsn(i,s,e) for(int i = s; i < e; i++)
#define rforn(i,s) for(int i = s; i >= 0; i--)
#define rforsn(i,s,e) for(int i = s; i >= e; i--)
#define iter(it,a,b) for(a::iterator it=b.begin(); it!=b.end();++it)
#define clz(a) __builtin_clz(a) // count leading zeroes
#define ctz(a) __builtin_ctz(a) // count trailing zeroes
#define popc(a) __builtin_popcount(a) // count set bits (binary me 1 kitne hai) (if longlong popcount ll)
#define ln "\n"
#define dbg(x) cerr<<#x<<" = "<<x<<endl
#define dbg2(x,y) cerr<<#x<<" = "<<x<<" & "<<#y<<" = "<<y<<endl;
#define dbgstl32(v) cerr<<#v<<" = \n"; { int c=0; forstl(it,v) \
cerr<<"    Term "<< ++c <<" = "<<it<<ln;} cerr<<endl
#define dbgstlp32(v) cerr<<#v<<" = \n"; { int c=0; forstl(it,v) \
cerr<<"    Term "<< ++c <<" = "<<it.fi<<" , "<<it.se<<ln;} cerr<<endl
#define dbgarr(v,s,e) cerr<<#v<<" = "; forsn(i,s,e) cerr<<v[i]<<", "; cerr<<endl
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(n) n.begin() , n.end() 
#define tfi first.first
#define tse first.second
#define tth second
typedef long long ll;
typedef long double ld;
typedef pair<int,int> p32; 
typedef pair<ll,ll> p64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
typedef map<int,int> m32;
typedef pair< pair<int,int> , int> tri;
typedef vector<bool> vbool;
typedef priority_queue<p32> pq32;
typedef priority_queue<p32, vector<p32>, greater<p32> > pq32l;

#pragma GCC optimize ("-O2")
const ll LIM = 2e5+5;
const ll MOD = 1e9+7;
const ll inf = 1e10;



int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	int n;
	cin >> n;

	double p[n];

	forn(i,n) cin >> p[i];

	double dp[n+1][n+1];

	forn(i,n) dp[0][i+1] = 0;
	dp[0][0] = 1;
	forn(i,n) dp[i+1][0] = dp[i][0]*(1-p[i]);

	forn(j,n) forn(i,n) {
		dp[i+1][j+1] = (dp[i][j+1]*(1-p[i])) + (dp[i][j]*(p[i]));
	}

	double ans = 0;

	forsn(i, n/2, n) ans += dp[n][i+1];

	cout << setprecision(20) << ans;


}


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

typedef long long ll;
const int maxn = 100010;
int n, X, b[maxn], l[maxn], r[maxn], p[maxn];
ll s[maxn];

int main() {
    cin >> n >> X;
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> b[i] >> l[i] >> r[i];
        s[i] = 1LL * b[i] * l[i] + 1LL * (X - b[i]) * r[i];
        p[i] = i, sum += 1LL * b[i] * l[i];
    }
    if (!sum) { cout << 0 << endl; return 0; }
    sort(p + 1, p + n + 1, [&](int x, int y) { return s[x] > s[y]; });
    ll lb = 1, rb = 1LL * n * X, ans;
    while (lb <= rb) {
        ll mid = (lb + rb) >> 1;
        auto chk = [&](ll x) {
            auto calc = [&](int pos, ll tmp) {
                if (tmp <= b[pos]) return 1LL * tmp * l[pos];
                else return 1LL * b[pos] * l[pos] + 1LL * (tmp - b[pos]) * r[pos];
            };
            ll ans = 0, cur = 0;
            int r = x % X;
            if (!r) r = X;
            int cnt = (x - r) / X;
            for (int i = 1; i <= n; i++) {
                if (i <= cnt) {
                    cur += s[p[i]];
                } else {
                    ans = max(ans, cur + calc(p[i], r));
                }
            }
            cur += s[p[cnt + 1]];
            for (int i = 1; i <= cnt; i++) {
                ans = max(ans, cur - s[p[i]] + calc(p[i], r));
            }
            return ans;
        };
        chk(mid) >= sum ? rb = (ans = mid) - 1 : lb = mid + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(n) begin(n),end(n)
using ll = long long;
using P = pair<int,int>;
const long long INF = 1LL << 60;
using namespace std;
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; }

ll dp[100010];

int main() {
    int n;
    cin >> n;
    vector<int> h(n);
    rep(i,n) cin >> h[i];
    rep(i,100010)dp[i] = INF;
    dp[0]=0;
    for(int i = 1; i < n; ++i){
        chmin(dp[i], dp[i-1] + abs(h[i]-h[i-1]));
        if(i>1) chmin(dp[i], dp[i-2] + abs(h[i]-h[i-2]));
    }
    cout << dp[n-1] << endl;
    return 0;
}

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

/*----------------------------- DEFINES ------------------------------*/

#define eps 1e-9
#define mod 1000000007
#define ump unordered_map // operations take less time compared to map
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define mp make_pair
#define ps(x) push(x) // for stack and queue
#define T top() //  for stack
#define FR front()// for queue
#define BA back()// for queue
#define PP pop()// for queue and stack
#define B begin()
#define E end()
#define F first
#define S second
#define tostr(x) to_string(x)
#define SZ(x) ((int)x.size())
#define ins insert
#define MAE max_element
#define MIE min_element
#define cnt(x) count(x)
#define lb(x) lower_bound(x) // returns an it ptng to the element >=x if no such returns end
#define ub(x) upper_bound(x) // returns an it ptng to the element >x if no such returns end
#define rep(i,x,y) for(int i=x;i<y;i++)
#define per(i,x,y) for(int i=x;i>y;i--)
#define repi(i,x,y) for(int i=x;i<=y;i++)
#define peri(i,x,y) for(int i=x;i>=y;i--)
#define reps(i,x,y,k) for(int i=x;i<y;i+=k)
#define sper(i,x,y,k) for(int i=x;i>y;i-=k) 
#define all(x) ((x.B),(x.E))
#define inf (ll)LLONG_MAX
#define ds1(i,x) for(auto i=x.begin();i!=x.end();i++)
#define ds2(i,x) for(auto i:x) // easy method to iterate through a ds
#define sq(a) (a)*(a)
#define fib(n) ceil(pow((1+sqrt(5),n)-pow((1-sqrt(5),n)/(float)(pow(2,n)*sqrt(5)// compute fib(n) in O(1)
#define FIO {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}// fast i/o
#define dig(n) (int)(log10(n)+1) // num of digits
#define ss(x,k) substr(x,k)  // x is the start pos and k is the length of substr.
#define f(x) find(x)
#define set(x,k) memset(x,k,sizeof x)

/*------------------------------ TYPEDEFS-----------------------------*/

typedef long long ll;
typedef long l;
typedef string str;
typedef vector<int> vi;
typedef vector<ll> vlli;
typedef vector<pair<int,int> > vpii;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef ump<int,int> umpii;

/*-----------------------------START FROM HERE -----------------------*/

int main(){
	FIO
	
	str s;cin>>s;
	str res="";
	rep(i,0,SZ(s)){
		if(s[i]=='0')res+="0";
		else if(s[i]=='1')res+='1';
		else{
			if(res.compare("")!=0)res.erase(res.end()-1);
		}
	}
	cout<<res;
	
	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
using namespace std;
using i64 = int64_t;
#define rep(i, j, n) for(int i = (j); i < (n); ++i)
#define rrep(i, j, n) for(int i = (n) - 1; (j) <= i; --i)
constexpr i64 MOD = 1000000007;
constexpr i64 INF = 1LL << 60;

int main() {

	i64 n, m, k; cin >> n >> m >> k;
	vector<i64> a(n), b(m);
	rep(i, 0, n) cin >> a[i];
	rep(i, 0, m) cin >> b[i];

	vector<i64> sa(n + 1), sb(m + 1);
	rep(i, 0, n) sa[i + 1] = sa[i] + a[i];
	rep(i, 0, m) sb[i + 1] = sb[i] + b[i];


	i64 ans = 0;
	rep(i, 0, n + 1) {
		// aをi札
		i64 diff = k - sa[i];
		if (diff < 0) break;
		i64 bn = upper_bound(sb.begin(), sb.end(), diff) - sb.begin();
		--bn;
		ans = max(ans, i + bn);
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 9588
#include  <iostream>
#include  <stdio.h>
#include <algorithm>
using namespace std;
#include <vector>
//#include <stack>
//#include <queue>

/*
#include <math.h>
int standerd = int(pow(10.0,9.0)) + 7;
*/
string ans_Yes = "Yes"; 
string ans_No = "No"; 
string ans_yes = "yes"; 
string ans_no = "no"; 
 

int main(){

    int N;
    
    cin >> N;

    vector<int> A;
    for( int ni = 0 ; ni < N ; ni++ ){
        int tmp;
        cin >> tmp;
        A.push_back(tmp - (ni + 1) );
    }
    sort(A.begin(),A.end());

    int index;
    int b;
    long long score;
    long long ans;
    if(N==1){
        ans = 0;
    }else{
        if(N%2==0){
            index = N /2 - 1;
            b = A[index];
            score=0;
            for( int ni = 0 ; ni < N ; ni++ ){
                score += abs(A[ni]-b);
            }
            ans = score;

            index = N /2 - 1 + 1;
            b = A[index];
            score=0;
            for( int ni = 0 ; ni < N ; ni++ ){
                score += abs(A[ni]-b);
            }
            ans = min(ans,score);

        }else{
            index = (N + 1) /2 - 1;
            b = A[index];
            score=0;
            for( int ni = 0 ; ni < N ; ni++ ){
                score += abs(A[ni]-b);
            }
            ans = score;
        }
    }
    cout << ans << endl;

}

Measured memory_bytes: 1400
#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define erep(e,v) for(auto && e :v)
#define all(in) in.begin(), in.end()
#define MP make_pair
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
#define EPS 0.0000000001
using namespace std;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
template<class T> void join(T a){for(auto itr :a){if(itr != *a.begin())cout << " "; cout << itr;} }
using ld  = long double;
using pii = pair<int,int>;
using piii = pair<int,pii>;
int W,H;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
bool valid(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}
signed main(){
    int a,b;
    double x = 0,y = 0;
    int arg = 90;
    char s;
    while(cin >> a >> s >> b,a or b){
        x += a * cos(arg * acos(-1) /180);
        y += a * sin(arg * acos(-1) /180);
        arg -= b;
        arg = (arg+360) % 360;
    }
    cout << (int)x << endl << (int) y << endl;
}





Measured memory_bytes: 3468
#include <cstdio>
#include <algorithm>

using namespace std;

//#define DEBUG

int N, T;
int A[3005], B[3005];
int ans;

int maxHappinessStart[3005][3005];
int maxHappinessEnd[3005][3005];

int main()
{
	scanf("%d%d", &N, &T);
	for (int i = 1; i <= N; i++) scanf("%d%d", A + i, B + i);
	for (int i = 0; i <= N; i++)
    {
        for (int j = 0; j < T; j++)
        {
            if (i == 0) maxHappinessStart[i][j] = 0;
            else if (j < A[i]) maxHappinessStart[i][j] = maxHappinessStart[i - 1][j];
            else
            {
                maxHappinessStart[i][j] = max(maxHappinessStart[i - 1][j], maxHappinessStart[i - 1][j - A[i]] + B[i]);
            }
        }
    }
	for (int i = N + 1; i > 0; i--)
    {
        for (int j = 0; j < T; j++)
        {
            if (i == N + 1) maxHappinessEnd[i][j] = 0;
            else if (j < A[i]) maxHappinessEnd[i][j] = maxHappinessEnd[i + 1][j];
            else
            {
                maxHappinessEnd[i][j] = max(maxHappinessEnd[i + 1][j], maxHappinessEnd[i + 1][j - A[i]] + B[i]);
            }
        }
    }

    #ifdef DEBUG
    printf("Max happiness start:\n");
    for (int i = 1; i <= N; i++)
    {
        for (int j = 0; j <= T; j++)
        {
            if (maxHappinessStart[i][j] != 0)
            {
                printf("maxHappinessStart[%d][%d]: %d\n", i, j, maxHappinessStart[i][j]);
            }
        }
    }
    printf("\nMax happiness end:\n");
    for (int i = 1; i <= N; i++)
    {
        for (int j = 0; j <= T; j++)
        {
            if (maxHappinessEnd[i][j] != 0)
            {
                printf("maxHappinessEnd[%d][%d]: %d\n", i, j, maxHappinessEnd[i][j]);
            }
        }
    }
    #endif // DEBUG

    ans = 0;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 0; j < T; j++)
        {
            ans = max(ans, maxHappinessStart[i - 1][j] + maxHappinessEnd[i + 1][T - 1 - j] + B[i]);
        }
    }
	printf("%d\n", ans);
}


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

using namespace std;

typedef long long ll;

const int INF = 1000000000;

int main()
{
  int a, b;
  scanf("%d %d", &a, &b);
  vector<string> board(100, string(100, '#'));
  for (int i = 50; i < 100; ++i) {
    board[i] = string(100, '.');
  }
  --a;
  for (int r = 0; r < 49 && a > 0; r += 2) {
    for (int c = 0; c < 100 && a > 0; c += 2) {
        board[r][c] = '.';
        --a;
    }
  }
  --b;
  for (int r = 51; r < 100 && b > 0; r += 2) {
    for (int c = 0; c < 100 && b > 0; c += 2) {
        board[r][c] = '#';
        --b;
    }
  }

  printf("100 100\n");
  for (int i = 0; i < 100; ++i) {
    printf("%s\n", board[i].c_str());
  }

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main()
{
    int m,f,r;
    while(1){
        scanf("%d%d%d",&m,&f,&r);
        if(m==-1&&f==-1&&r==-1)break;
        if(m==-1||f==-1)printf("F\n");
        else if(m+f>=80)printf("A\n");
        else if(m+f>=65)printf("B\n");
        else if(m+f>=50)printf("C\n");
        else if(m+f>=30){
            if(r>=50)printf("C\n");
            else printf("D\n");
        }
        else printf("F\n");
    } 
}


Measured memory_bytes: 3136
import java.util.Scanner;                                                                     
class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(true){
            int h = in.nextInt();
            int w = in.nextInt();
            if(h == 0 && w == 0){
                break;
            }
            for(int i=0; i<h; i++){
                for(int j=0; j<w; j++){
                    if(i == 0 || i == h-1){
                        System.out.print("#");
                    }else if(j == 0 || j == w-1){
                        System.out.print("#");
                    }else{
                    System.out.print(".");
                    }
                }
                System.out.print("\n");
            }
            System.out.print("\n");
         }
     }
}               

Measured memory_bytes: 37392
def run(a, b, k):
    ans1 = a - k
    ans2 = b
    if ans1 < 0:
        ans2 = b + ans1
        ans1 = 0
    if ans2 < 0:
        ans2 = 0
    return ans1, ans2


def main():
    a, b, k = map(int, input().split())
    ans = run(a, b, k)
    print(ans[0], ans[1])


if __name__ == '__main__':
    main()

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

using i32 = std::int_fast32_t;
using i64 = std::int_fast64_t;
template <typename T> constexpr T inf = numeric_limits<T>::has_infinity ? numeric_limits<T>::infinity() : numeric_limits<T>::max() / 4;

#define REP(i, stop) FOR(i, 0, stop)
#define FOR(i, start, stop) for (int i = start, i##_len = stop; i < i##_len; ++i)
#define RREP(i, n) for (int i = n; i-- > 0;)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define COMP(key) [](const auto& a, const auto& b) { return a.key < b.key; }

template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& a) { return is >> a.first >> a.second; }
template<typename T> istream& operator>>(istream& is, vector<T>& a) { for (T& x : a) is >> x; return is; }

template<typename T> using pop_max = std::priority_queue<T>;
template<typename T> using pop_min = std::priority_queue<T, std::vector<T>, std::greater<T>>;

void LOG(const int& x) { cerr << x << "\n"; }
template<typename T> void LOG(const vector<T>& a) { for (const T& x : a) cerr << x << " "; cerr << "\n"; }
template<typename T, std::size_t S> void LOG(const T (&a)[S]) { REP(i, S) cerr << a[i] << " "; cerr << "\n"; }
template<typename T, std::size_t S, std::size_t R> void LOG(const T (&a)[S][R]) { REP(i, S) { REP(j, R) cerr << a[i][j] << " "; cerr << "\n"; } }

i64 ceil(i64 a, i64 b) { return (a - 1) / b + 1; }
i64 gcd(i64 a, i64 b) { while (b != 0) { i64 t = b; b = a % b; a = t; } return a; }
i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
i64 gcd(const vector<i64>& v) { return accumulate(ALL(v), 1LL, static_cast<i64(*)(i64, i64)>(gcd)); }
i64 lcm(const vector<i64>& v) { return v.empty() ? 0LL : accumulate(v.begin() + 1, v.end(), v[0], static_cast<i64(*)(i64, i64)>(lcm)); }
i64 pow(i64 x, i64 y, i64 z) { i64 a = 1; while (y > 0) { if (y & 1) a = a * x % z; x = x * x % z; y /= 2; } return a; }
i64 inv(i64 x, i64 m) { return pow(x, m - 2, m); }

struct InitCpp { InitCpp() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); } } initCpp;

const i64 INF = inf<i64>;
using P = pair<i64, i64>;
using T = pair<i64, P>;
const i64 M = 1000000007;
signed main() {
  i64 n,d,a;
  cin>>n>>d>>a;
  vector<P> xh(n);
  cin>>xh;
  sort(ALL(xh));
  i64 s=0;
  i64 l=0;
  i64 ans=0;
  pop_min<P> que;
  REP(i,n){
    while(que.size()&&que.top().first<xh[i].first){
      s-=que.top().second;
      que.pop();
    }
    if(xh[i].second-s*a>0){
      i64 c=ceil(xh[i].second-s*a,a);
      s+=c;
      ans+=c;
      l=xh[i].first;
      que.push({l+d*2,c});
    }
  }
  cout<<ans<<endl;
}


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

int main() {
  int N;
  cin >> N;
  priority_queue<double, vector<double>, greater<double>> que;
  rep(i, N) {
    int v;
    cin >> v;
    que.push(v);
  }
  while (!que.empty()) {
    double v1 = que.top();
    que.pop();
    if (que.empty()) {
      cout << v1 << endl;
      return 0;
    }
    double v2 = que.top();
    que.pop();
    que.push((v1 + v2) / 2);
  }
}

Measured memory_bytes: 3740
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <utility>
#include <complex>
#include <functional>
using namespace std;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<int, int> p;
const int INF = (1 << 28);
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
int n, m, q;
vector<p> z;
vector<p> que;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m >> q;
    int sum[n][n];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            sum[i][j] = 0;
    }
    for (int i = 0; i < m; i++)
    {
        int temp1, temp2;
        cin >> temp1 >> temp2;
        sum[temp1 - 1][temp2 - 1]++;
    }
    int sum1[n][n];
    sum1[0][0] = sum[0][0];
    for (int i = 1; i < n; i++)
    {
        sum1[0][i] = sum1[0][i - 1] + sum[0][i];
    }
    for (int i = 1; i < n; i++)
    {
        sum1[i][0] = sum1[i - 1][0] + sum[i][0];
    }
    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j < n; j++)
        {
            sum1[i][j] = sum1[i - 1][j] + sum1[i][j - 1] + sum[i][j] - sum1[i - 1][j - 1];
        }
    }
    vector<int> ansv;
    for (int i = 0; i < q; i++)
    {
        int q1, q2;
        int ans = 0;
        cin >> q1 >> q2;
        q1--;
        q2--;
        if (q1 != 0)
            ans = sum1[q2][q2] + sum1[q1 - 1][q1 - 1] - sum1[q2][q1 - 1] - sum1[q1 - 1][q2];
        else
        {
            ans = sum1[q2][q2];
        }

        ansv.push_back(ans);
    }
    for (int i : ansv)
    {
        cout << i << "\n";
    }
}


Measured memory_bytes: 3448
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define FOR(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
#define MOD 1000000007
 
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
template <class T>
void print(T& x){printf("%d\n", x);}

struct Node{
    int num;
    Node *left;
    Node *right;
};

ll calc_length(Node *node, int depth){
    if(node->left==NULL){
        return depth * node->num;
    }
    return calc_length(node->left, depth+1) + calc_length(node->right, depth+1);
}

// void print_length(Node *node, int depth){
//     if(node->left==NULL){
//         printf("(%d %d)\n", node->num, depth);
//         return;
//     }
//     print_length(node->left, depth+1);
//     print_length(node->right, depth+1);
// }

int coef(Node *p){
    if(p->left == NULL && p->right==NULL){
        return 1;
    }else{
        return 2;
    }
}


bool compare(Node* p1, Node* p2){
    return p1->num > p2->num;
}

int main()
{
    char S[100005];
    scanf("%s", S);
    unordered_map<char, int> dict_u;
    int n_len=0;
    while(S[n_len] != '\0'){
        dict_u[S[n_len]]++;
        n_len++;
    }
    
    vector<Node*> num;  
    int n=0;
    for(auto i=dict_u.begin(); i!=dict_u.end(); i++){
        Node* p=(Node*)malloc(sizeof(Node));
        p->num=i->second; p->left=NULL; p->right=NULL;
        num.emplace_back(p);
        n++;
    }

    sort(ALL(num), compare);
    
    for(int i=n-1; i>0; i--){
        // REP(j, i+1) printf("%d ", num[j]->num);
        // printf("\n");
        Node *right=num[i], *left=num[i-1];
        Node *newnode = (Node*)malloc(sizeof(Node));
        newnode->num = (right->num) + (left->num);

        newnode->left = left; newnode->right = right;
        // printf("right.num = %d, length=%d\n", right->num, right->length);
        // printf("left.num = %d, length=%d\n", left->num, left->length);
        // printf("newnode.num = %d\n", (right->num) + (left->num));
        num[i-1] = newnode;

        sort(num.begin(), num.begin()+i, compare);
    }
    // printf("%d\n", num[0]->num);
    Node *head = num[0];
    if(head->left == NULL){
        printf("%d\n", num[0]->num);
    }
    else{
        printf("%lld\n", calc_length(head, 0));
        // print_length(head, 0);
    }

    return 0;
}


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

int bubbleSort(int *,int);

int main()
{
  int n,*m,i,c,j;
  
  scanf("%d",&n);

  m = (int *)malloc(n * sizeof(int));

  for(i=0;i<n;i++){
    scanf("%d",&m[i]);
  }

  c = bubbleSort(m,n);

  for(j=0;j<n;j++){
    printf("%d",m[j]);
    if(j<n-1) printf(" ");
    else printf("\n");
  }
  printf("%d\n",c);

  free(m);

  return 0;
}

int bubbleSort(int *m,int n)
{
  int i,j,t,c=0;
  for(i=0;i<n;i++){
    for(j=n-1;j>i;j--){
      if(m[j-1]>m[j]){
	t = m[j-1];
	m[j-1] = m[j];
	m[j] = t;
	c++;
      }
    }
  }

  return c;
}



  
    



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

int main()
{
  long int i,j,n,m;
  cin>>n;
  vector<long int>h(n);
  for(i=0;i<n;i++)
    cin>>h[i];
  vector<long int>v(n,0);
  v[1]=abs(h[0]-h[1]);
  for(i=2;i<n;i++)
    v[i]=min(abs(h[i]-h[i-1])+v[i-1],abs(h[i]-h[i-2])+v[i-2]);
  cout<<v[n-1]<<"\n";
 return 0;
}



Measured memory_bytes: 4852
#include <iostream>
#include <cmath>
#include <algorithm>
#define rep(i,n) for(int i = 0; i < n;i++)
using namespace std;
int X[100005],A[100005];
int main(){
    int T;
    cin >> T;
    rep(t,T){
        int ans = 0;
        int N,K;
        cin >> N >> K;
        rep(i,N){
            cin >> X[i];
        }
        rep(i,N-1){
            A[i]=  X[i+1]-X[i];
        }
        sort(A,A+N-1);
        int m = (N-1)-(K-1);
        rep(i,m){
            ans += A[i];
        }
        cout << ans << endl;
    }
}

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

int main(){
    int N;
    cin>>N;
    vector<ll>X(N);
    vector<ll>Y(N);
    rep(i,N){
        ll x,y;
        cin>>x>>y;
        X[i]=x-y;
        Y[i]=x+y;
    }
    sort(X.begin(),X.end());
    sort(Y.begin(),Y.end());
    ll S=X[N-1]-X[0];
    ll T=Y[N-1]-Y[0];
    cout<<max(S,T)<<endl;
}

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

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    double r, c;

    cin >> r;

    c = 2 * 3.1416 * r;
    cout << c << "\n";
    return 0;
}


Measured memory_bytes: 3784
#include<bits/stdc++.h>
#include <numeric>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define fs first
#define sc second
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<tuple<ll,ll>> vtl;
typedef pair<ll, ll> l_l;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
#define pf(a) cout << (a) << endl;
#define be(x) (x).begin(),(x).end()
bool is_prime(ll n){
    if(n==2)return true;
    else if(n<2||n%2==0)return false;
    ll i=3;
    while(i<=sqrt(n)){
        if(n%i==0)return false;
        i+=2;
    }
    return true;
}
ll merge_cnt(vector<int> &a) {
    int n = a.size();
    if (n <= 1) { return 0; }

    ll cnt = 0;
    vector<int> b(a.begin(), a.begin()+n/2);
    vector<int> c(a.begin()+n/2, a.end());

    cnt += merge_cnt(b);
    cnt += merge_cnt(c);

    int ai = 0, bi = 0, ci = 0;
    // merge の処理
    int ans=0;
    while (ai < n) {
        if ( bi < b.size() && (ci == c.size() || b[bi] <= c[ci]) ) {
            continue;
        } else {
            cnt += n / 2 - bi;
            a[ai++] = c[ci++];
        }
        if(cnt!=0){
        ans++;
        cnt=0;
    }
    }
    
    return ans;
}
void solve(){
    ll h,n;
    cin>>h>>n;
    vl a(n),b(n);
    rep(i,n)cin>>a[i]>>b[i];
    vl dp(h+1,10e9);
    dp[0]=0;
    rep(i,n)rep(j,h)dp[min(j+a[i],h)]=min(dp[j]+b[i],dp[min(j+a[i],h)]);
    cout<<dp[h]<<endl;
}
int main(){
    cout<<std::fixed<<std::setprecision(10);
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

Measured memory_bytes: 384