akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <functional>

using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
void dfs(int N,vector<int> G[],function<void(int,int,int)> F){
	stack<pair<int,int>> sp;
	sp.push({0,-1});
	while(!sp.empty()){
		int v = sp.top().first;
		int f = sp.top().second;
		sp.pop();
		for(int i=0;i<G[v].size();i++){
			int t = G[v][i];
			if(t != f){
				F(t,v,i);
				sp.push({t,v});
			}
		}
	}
}
vector<int> G[100000];
vector<bool> C[100000];
bool ans[100000];
void Calc(){
	int N = rei();
	for(int i=0;i<N-1;i++){
		int f = rei()-1;
		int t = rei()-1;
		int w = rei();
		C[f].push_back(w % 2 == 1);
		C[t].push_back(w % 2 == 1);
		G[f].push_back(t);
		G[t].push_back(f);
	}
	function<void(int,int,int)> F = [&](int t,int v,int i){
		if(C[v][i]){
			ans[t] = !ans[v];
		}
		else{
			ans[t] = ans[v];
		}
	};
	dfs(N,G,F);
	for(int i=0;i<N;i++){
		if(ans[i]){
			cout << "0\n";
		}
		else{
			cout << "1\n";
		}
	}
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}

Measured memory_bytes: 13056
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using ll = long long;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using P = pair<ll, ll>;

// chmin, chmax関数
template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}
template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}

// Yes-Noを出力する問題で楽をする
void Ans(bool f){
    if(f) cout << "Yes" << endl;
    else cout << "No" << endl;
}

//---------------------------

int main(){
    string s;
    cin >> s;
    int ans = 0;
    rep(i,4){
        if(s[i]=='+') ans++;
        else ans--;
    } 
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
N, C = map(int, input().split())
D = [list(map(int, input().split())) for i in range(C)]
c = [list(map(int, input().split())) for i in range(N)]

d = [[0 for j in range(C)] for i in range(3)]
for i in range(N):
    for j in range(N):
        m = (i+j) % 3
        cc = c[i][j]-1
        for k in range(C):
            d[m][k] += D[cc][k]

res = 2*10**9
for i in range(C):
    for j in range(C):
        if i == j: continue
        for k in range(C):
            if k in (i, j): continue
            res = min(res, d[0][i]+d[1][j]+d[2][k])
else:
    print(res)


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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int INT_INF = 2147483647;
const long long LL_INF = 1LL<<60;
const long long MOD = 1000000007;

#define CLR(a) memset((a), 0 ,sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << 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; }

int main(void){
    int K; cin >> K;
    cout << (K%2 ? (K+1)/2 * (K-1)/2 : K/2 * K/2) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n,ans=0;
    long double d,x,y,l;
    cin>>n>>d;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        l=sqrt(x*x+y*y);
        if(l<=d){
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3844
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x1 = sc.nextInt();
		int y1 = sc.nextInt();
		int x2 = sc.nextInt();
		int y2 = sc.nextInt();

		int x = x1 - x2;
		int y = y1 - y2;

		int x3 = x2 + y;
		int y3 = y2 - x;

		int x4 = x3 + x;
		int y4 = y3 + y;

		System.out.println(x3 +" "+ y3 +" "+ x4 + " " + y4);
		sc.close();
	}

}


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

int main()
{
    string s,t;
    cin>>s>>t;
    int count=0;
    for(int i=0;i<s.size();i++){
        if(s[i]!=t[i]){
            count++;
        }
    }
    cout<<count<<endl;
}

Measured memory_bytes: 3912
#include<iostream>
#include<queue>
#include<string>
using namespace std;
int n; string a[100], b[100], S, T;
queue<pair<string, int> >Q;
int main() {
	while (true) {
		cin >> n; if (n == 0)break;
		for (int i = 0; i < n; i++)cin >> a[i] >> b[i];
		cin >> S >> T;
		while (!Q.empty())Q.pop();
		Q.push(make_pair(S, 0));
		while (!Q.empty()) {
			pair<string, int> U = Q.front(); Q.pop();
			string W = U.first;
			if (T == W) { cout << U.second << endl; goto E; }
			for (int i = 0; i < n; i++) {
				string V = W;
				for (int j = 0; j <= (int)V.size() - (int)a[i].size(); j++) {
					if (V.substr(j, a[i].size()) == a[i]) {
						V = V.substr(0, j) + b[i] + V.substr(j + a[i].size(), V.size() - (j + a[i].size()));
						j += b[i].size() - 1;
					}
				}
				if (W != V && V.size() <= T.size()) {
					Q.push(make_pair(V, U.second + 1));
				}
			}
		}
		cout << "-1" << endl;
	E:;
	}
	return 0;
}

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

//const long double PIL = 3.141592653589793238462643383279502884L;
//const double PI = 3.14159265358979323846;

#define sz(a) int((a).size())
#define all(c) (c).begin(), (c).end()
#ifdef LOCAL
#define what_is(x) cerr << #x << " is " << x << endl;
#define debug(v) {for (auto x : v) cerr << x << ' '; cerr << endl;}
#else
#define what_is(x)
#define debug(v)
#endif

using ll = long long;
using ii = pair<int,int>;
using vi = vector<int>;
using vll = vector<long long>;
using vii = vector<pair<int,int>>;

const int INF = 1e9;
const int N = 2505;
vi rev[N];
bool visited[N];

void dfs(int u) {
	visited[u] = true;
	for (int v : rev[u])
		if (!visited[v]) dfs(v);
}

int main() {
	//~ ios::sync_with_stdio(0);
	//~ cin.tie(0);
	int n, m, p;
	scanf("%d%d%d", &n, &m, &p);
	vector<tuple<int,int,int>> edge(m);
	for (int i = 0; i < m; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		edge.emplace_back(u, v, w-p);
		rev[v].push_back(u);
	}

	vi dist(n+1, -INF);
	dist[1] = 0;
	for (int i = 0; i < n-1; i++) {
		for (auto e : edge) {
			int u, v, w;
			tie(u, v, w) = e;
			if (dist[u] != -INF) dist[v] = max(dist[v], dist[u] + w);
		}
	}

	dfs(n);
	for (auto e : edge) {
		int u, v, w;
		tie(u, v, w) = e;
		if (dist[u] != -INF && dist[v] < dist[u] + w && visited[v]) {
			puts("-1");
			return 0;
		}
	}
	printf("%d\n", max(0, dist[n]));
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define p_b push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
using namespace std;

int main()
{
    ll x;
    cin >> x;
    cout << (x/500)*1000 + ((x%500)/5)*5;
}


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

using namespace std;

const int maxn=1400;

int dp[maxn][maxn],g[maxn][maxn];

int getlargestsquare(int h,int w)
{
    int maxwidth=0;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            dp[i][j]=(g[i][j]+1)%2;
            //只有一行的情况
            maxwidth|=dp[i][j];
        }
    }
    for(int i=1;i<h;i++){
        for(int j=1;j<w;j++){
            if(g[i][j]){
                dp[i][j]=0;
            }else{
                //本道题的关键
                dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
                maxwidth=max(maxwidth,dp[i][j]);
            }
        }
    }
    return maxwidth*maxwidth;
}

int main()
{
    int h,w;
    cin>>h>>w;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>g[i][j];
        }
    }
    printf("%d\n",getlargestsquare(h,w));
    return 0;
}



Measured memory_bytes: 18392
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long ll;

int main()
{
	ll a,b,c;
	scanf("%lld%lld%lld",&a,&b,&c);
	if((a&1) && (b&1) && (c&1))
	{
		if(a>b)swap(a,b);
		if(a>c)swap(a,c);
		if(b>c)swap(b,c);
		printf("%lld\n",a*b);
	}
	else
		puts("0");

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>

int main () {
  int a, b;
  char op;
  char ops[5] = {'+', '-', '*', '/', '?'};
  std::vector<int> ans;
  while (std::cin >> a >> op >> b)
  {
    if (op == ops[0])
    {
      std::cout << a + b << std::endl;
      // ans.push_back(a + b);
    }
    if (op == ops[1])
    {
      std::cout << a - b << std::endl;
      // ans.push_back(a - b);
    }
    if (op == ops[2])
    {
      std::cout << a * b << std::endl;
      // ans.push_back(a * b);
    }
    if (op == ops[3])
    {
      std::cout << a / b << std::endl;
      // ans.push_back(a / b);
    }
    if (op == ops[4])
    {
      break;
    }
  }
  // for (int const& res : ans) {
  //   std::cout << res << std::endl;
  // }
  return 0;
}


Measured memory_bytes: 3088
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include<stack>
#include <queue>
#include<map>
#include <set>
using namespace std;
#define int long long
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define loop(i,m,n) for(ll i=m;i<n;++i)
#define ggr getchar(); getchar();return 0;
#define pie 3.141592653589793238462643383279
#define INF 1000000007
int bin(int bina) {
	int ans = 0;
	for (int i = 0; bina > 0; i++)
	{
		ans = ans + (bina % 2)*pow(10, i);
		bina = bina / 2;
	}
	return ans;
}
bool prime(int n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int jo(int n) {
	int ans = 1;
	rep(i, n) {
		ans *= 2;
	}
	return ans;
}

signed main() {
	int a;
	cin >> a;
	cout << a / 2 * (a - a / 2) << endl;
}


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

int n, x[55], y[55];
set<pair<int, int>> s;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d%d", x + i, y + i), s.emplace(x[i], y[i]);
	if (n == 1) return puts("1"), 0;
	int ans = 1 << 30;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			if (j != i) {
				int p = x[j] - x[i], q = y[j] - y[i];
				int cnt = 0;
				for (int i = 1; i <= n; ++i)
					if (!s.count(make_pair(x[i] + p, y[i] + q)))
						++cnt;
				ans = min(ans, cnt);
			}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<limits>
#include<cmath>
using namespace std;
int N,M;
int n[51],m[51];
int nx[51],ny[51];
int cx[51],cy[51];
int main(){
	cin>>N>>M;
	for(int i=0;i<N;i++){
		cin>>nx[i]>>ny[i];
	}
	for(int i=1;i<=M;i++){
		cin>>cx[i]>>cy[i];
	}
	for(int i=0;i<N;i++){
		int mi,mid=1000000000;
		for(int j=1;j<=M;j++){
			if(abs(nx[i]-cx[j])+abs(ny[i]-cy[j])<mid){
				mid=abs(nx[i]-cx[j])+abs(ny[i]-cy[j]);
				mi=j;
			}
		}
		cout<<mi<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
import numpy as np
from decimal import Decimal, getcontext
getcontext().prec = 50
a, b, c = map(int, input().split())
if Decimal(Decimal(2) * Decimal(np.sqrt(Decimal((Decimal(a)*Decimal(b)))))) + Decimal(a) + Decimal(b) < Decimal(c):
    print("Yes")
else:
    print("No")


Measured memory_bytes: 13544
while True:
    H, W = map(int, input().split())
    if H == 0 and W == 0:
        break
    for i in range(H):
        if i == 0 or i == H - 1:
            print('#' * W)
        else:
            print('#' + '.' * (W - 2) + '#')
    print('')


Measured memory_bytes: 5608
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

typedef long long ll;
typedef pair<pair<pair<ll, ll>, ll>, pair<ll, ll>> P;

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

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

	ll h, w, k;cin >> h >> w >> k;
	ll x1, x2, y1, y2;cin >> y1 >> x1 >> y2 >> x2;
	x1--;x2--;y1--;y2--;
	vector<vector<char>> mp(h, vector<char>(w));
	vector<vector<vector<pair<ll, ll>>>> dist(h, vector<vector<pair<ll, ll>>>(w, vector<pair<ll, ll>>(4, MP(INF, INF))));
	REP(i, h)REP(j, w)cin >> mp[i][j];

	priority_queue<P, vector<P>, greater<P>> pq;
	REP(i, 4){
		pq.push(MP(MP(MP(1, 0), i), MP(y1, x1)));
		dist[y1][x1][i] = MP(1, 0);
	}
/*
	REP(i, h){
		REP(j, w){
			ll now = INF;
			REP(k, 4)now = min(now, dist[i][j][k].FI);
			cout << now << " ";
		}
		cout << endl;
	}
*/
	while(!pq.empty()){
		ll now_dist = pq.top().FI.FI.FI;
		ll now_cou = pq.top().FI.FI.SE;
		ll now_dir = pq.top().FI.SE;
		ll y = pq.top().SE.FI;
		ll x = pq.top().SE.SE;
		pq.pop();
		//cout << now_dist << " " << now_dir << " " << y << " " << x << endl;

		REP(i, 4){
			ll yy = y + dy[i];
			ll xx = x + dx[i];
			ll nxt_cou = (i == now_dir ? now_cou + 1 : 1);
			if(yy < 0 || xx < 0 || yy >= h || xx >= w)continue;
			if(mp[yy][xx] == '@')continue;
			ll cost = (i != now_dir);
			if(k < nxt_cou){
				cost = 1;
				nxt_cou = 1;
			}
			if(dist[yy][xx][i] <= MP(now_dist + cost, nxt_cou))continue;
			dist[yy][xx][i] = MP(now_dist + cost, nxt_cou);
			pq.push(MP(MP(MP(now_dist + cost, nxt_cou), i), MP(yy, xx)));
		}
	}

	ll ans = INF;
	REP(i, 4)ans = min(ans, dist[y2][x2][i].FI);
	if(ans == INF)cout << -1 << endl;
	else cout << ans << endl;
/*
	REP(i, h){
		REP(j, w){
			ll now = INF;
			REP(k, 4)now = min(now, dist[i][j][k].FI);
			cout << now << " ";
		}
		cout << endl;
	}
*/
	return 0;
}


Measured memory_bytes: 207364
n = int(input())
s_l = [int(input()) for _ in range(n)]
s_l.sort()
tot = 0
for val in s_l:
    tot += val
if tot%10 != 0:
    print(tot)
else:
    for val in s_l:
        if (tot-val)%10 != 0:
            print(tot-val)
            break
    else:
        print(0)

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

int main() {
    int nq;
    cin >> nq;

    auto a_left = multiset<int, greater<int>>();
    auto a_right = multiset<int>();
    auto a_cnt = 0;
    auto a_left_sum = 0LL;
    auto a_right_sum = 0LL;
    auto b_sum = 0LL;

    for (int i = 0; i < nq; ++i) {
        large type, a, b;
        cin >> type;

        if (type == 1) {
            cin >> a >> b;
            b_sum += b;
            ++a_cnt;

            if (a_left.empty()) {
                a_left.insert(a);
                a_left_sum += a;
            } else if (a_left.size() == a_right.size()) { // insert to left
                auto smallest_right = *a_right.begin();
                if (a <= smallest_right) {
                    a_left.insert(a);
                    a_left_sum += a;
                } else {
                    a_right.erase(a_right.begin());
                    a_right_sum -= smallest_right;
                    a_right.insert(a);
                    a_right_sum += a;

                    a_left.insert(smallest_right);
                    a_left_sum += smallest_right;
                }
            } else { // insert to right
                auto largest_left = *a_left.begin();
                if (a >= largest_left) {
                    a_right.insert(a);
                    a_right_sum += a;
                } else {
                    a_left.erase(a_left.begin());
                    a_left_sum -= largest_left;
                    a_left.insert(a);
                    a_left_sum += a;

                    a_right.insert(largest_left);
                    a_right_sum += largest_left;
                }
            }
        } else {
            // SUM( a[i] - a ) ---> SUM( a[i] ) - N*a
            // SUM( a - a[i] ) ---> N*a - SUM( a[i] )
            if (a_left.size() != (a_cnt + 1) / 2)
                throw - 1;
            if (a_left.size() + a_right.size() != a_cnt)
                throw - 1;

            auto a_mid = *a_left.begin();
            auto left_sum = a_left_sum - ((large)a_left.size() * a_mid);
            auto right_sum = a_right_sum - ((large)a_right.size() * a_mid);
            auto sum = -left_sum + right_sum;

            cout << a_mid << " " << (sum + b_sum) << "\n";
        }
    }

    return 0;
}


Measured memory_bytes: 9600
X, Y, A, B, C = map(int, input().split())
Ap = list(map(lambda x: (int(x), 0), input().split()))
Bq = list(map(lambda x: (int(x), 1), input().split()))
Cr = list(map(lambda x: (int(x), 2), input().split()))

INF = 2 * 10**5 + 1

L = Ap + Bq + Cr
L.sort(reverse = True)

cnt = [0, 0, 0]
cntM = [X, Y, INF]
s = 0

ans = 0

for x, i in L:
  if s == X + Y:
    break
  elif cnt[i] < cntM[i]:
    ans += x
    cnt[i] += 1
    s += 1
  else:
    pass

print(ans)

Measured memory_bytes: 117664
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int N, M;
int a, b, c, d;
int W, H;
string s;
vector<int> v;
int main() {
    cin >> N;
    int ans=0;
    for(int i=0; i<N; ++i){
        cin >> a >> b;
        ans += b-a+1;
    }
    cout << ans;
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define inf (1e9 + 7)
using namespace std;

int n, num[200005], sum[800020], sum2[800020], id[800020], id2[800020], ans, ans2, an = 0, du[200005];

struct node
{
    int a, b, id;
}ans3[200005];

vector<int> eg[200005];

inline void push_up(int a)
{
     if(sum[a * 2] < sum[a * 2 + 1])
        sum[a] = sum[a * 2], id[a] = id[a * 2];
     else
        sum[a] = sum[a * 2 + 1], id[a] = id[a * 2 + 1];
     if(sum2[a * 2] < sum2[a * 2 + 1])
        sum2[a] = sum2[a * 2], id2[a] = id2[a * 2];
     else
        sum2[a] = sum2[a * 2 + 1], id2[a] = id2[a * 2 + 1];
}

void build(int l, int r, int nn)
{
    sum[nn] = sum2[nn] = inf;
    if(l == r)
    {
        if(l&1)
            sum[nn] = num[l], id[nn] = l;
        else
            sum2[nn] = num[l], id2[nn] = l;
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, nn * 2);
    build(mid + 1, r, nn * 2 + 1);
    push_up(nn);
}

void get(int l, int r, int nn, int ll, int rr)
{
    if(l >= ll&&r <= rr)
    {
        if(ll&1)
        {
            if(ans > sum[nn])
                ans = sum[nn], ans2 = id[nn];
        }
        else
        {
            if(ans > sum2[nn])
                ans = sum2[nn], ans2 = id2[nn];
        }
        return;
    }
    if(l > rr||r < ll)
        return;
    int mid = (l + r) / 2;
    get(l, mid, nn * 2, ll, rr);
    get(mid + 1, r, nn * 2 + 1, ll, rr);
}

void solve(int l, int r, int fa)
{
    if(l > r)
        return;
    ans = inf;
    get(1, n, 1, l, r);
    int pos = ans2;
    ans = inf;
    get(1, n, 1, pos + 1, r);
    int pos2 = ans2;
    an++;
    ans3[an].a = num[pos];
    ans3[an].b = num[pos2];
    ans3[an].id = an;
    if(fa != -1)
        eg[fa].push_back(an), du[an]++;
    int tmp = an;
    solve(l, pos - 1, tmp);
    solve(pos + 1, pos2 - 1, tmp);
    solve(pos2 + 1, r, tmp);
    return;
}

struct cmp
{
    bool operator()(const node a, const node b)
    {
        if(a.a == b.a)
            return a.b > b.b;
        return a.a > b.a;
    }
};

int main()
{
    scanf("%d", &n);
    for(int i = 1;i <= n;i++)
        scanf("%d", &num[i]);
    build(1, n, 1);
    solve(1, n, -1);
    priority_queue<node, vector<node>, cmp> q;
    q.push(ans3[1]);
    bool ff = 0;
    while(!q.empty())
    {
        node u = q.top();
        q.pop();
        if(!ff)
            printf("%d %d", u.a, u.b), ff = 1;
        else
            printf(" %d %d", u.a, u.b);
        for(int i = 0;i < eg[u.id].size();i++)
        {
            int v = eg[u.id][i];
            du[v]--;
            if(du[v] == 0)
                q.push(ans3[v]);
        }
    }
    puts("");
    return 0;
}



Measured memory_bytes: 33536
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int number_a, number_b, number_c;
    number_a = Integer.parseInt(sc.next());
    number_b = Integer.parseInt(sc.next());
    number_c = Integer.parseInt(sc.next());
    if(number_a < number_b && number_b < number_c) System.out.println("Yes");
    else System.out.println("No");
  }
}


Measured memory_bytes: 26112
import sys
input = sys.stdin.readline

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

B=[]
C=[]
Z=[]
 
for a in A:
    if a>0:
        B.append(a)
    elif a<0:
        C.append(-a)
    else:
        Z.append(0)
 
B.sort(reverse=True)
C.sort(reverse=True)
 
if K==len(B)+len(C):
    ANS=1
    for b in B:
        ANS=ANS*b%mod
    for c in C:
        ANS=ANS*(-c)%mod
 
    if len(C)%2==1 and Z!=[]:
        print(0)
    else:
        print(ANS)
    sys.exit()
 
if K>len(B)+len(C):
    print(0)
    sys.exit()
 
if B==[]:
    if Z==[] and K%2==0:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
        print(ANS)
 
    elif Z==[] and K%2==1:
        ANS=1
        C.reverse()
        for i in range(K):
            ANS=ANS*(-C[i])%mod
        print(ANS)
        
    elif K%2==1:
        print(0)
        
    else:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
        print(ANS)
 
    sys.exit()

if K<=len(B):
    S=1
    for i in range(K):
        S=S*B[i]%mod

    ind=0
    while True:
        if ind+1<len(C) and K-2-ind>=0 and C[ind]*C[ind+1]>B[K-1-ind]*B[K-2-ind]:
            S=S*C[ind]*C[ind+1]*pow(B[K-1-ind]*B[K-2-ind],mod-2,mod)%mod
            ind+=2
        else:
            break

    print(S%mod)

else:
    if (K-len(B))%2==0:
        S=1
        for i in range(len(B)):
            S=S*B[i]%mod

        for j in range(K-len(B)):
            S=S*C[j]%mod

        ind=0
        c_start=K-len(B)

        while True:
            if c_start+ind+1<len(C) and len(B)-2-ind>=0 and C[c_start+ind]*C[c_start+ind+1]>B[len(B)-1-ind]*B[len(B)-2-ind]:
                S=S*C[c_start+ind]*C[c_start+ind+1]*pow(B[len(B)-1-ind]*B[len(B)-2-ind],mod-2,mod)%mod
                ind+=2
            else:
                break

    else:
        S=1
        for i in range(len(B)-1):
            S=S*B[i]%mod

        for j in range(K-len(B)+1):
            S=S*C[j]%mod

        ind=0
        c_start=K-len(B)+1

        while True:
            if c_start+ind+1<len(C) and len(B)-3-ind>=0 and C[c_start+ind]*C[c_start+ind+1]>B[len(B)-2-ind]*B[len(B)-3-ind]:
                S=S*C[c_start+ind]*C[c_start+ind+1]*pow(B[len(B)-2-ind]*B[len(B)-3-ind],mod-2,mod)%mod
                ind+=2
            else:
                break

    print(S%mod)
    


Measured memory_bytes: 31848
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define M_PI 3.14159265358979

int main(void){
    double num;
    //????????\???
    scanf("%lf",&num);
    double circumference=num*2*M_PI;
    double circlearea=num*num*M_PI;
    
    printf("%.6f %.6f\n",circlearea,circumference);

return 0;
}

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

int main()
{
    int a[20];
     for(int i=0;i<20;i++){
    cin>>a[i];
   }
  sort(a,a+10,greater<int>());
  sort(a+10,a+20,greater<int>());
  cout<<a[0]+a[1]+a[2]<<" "<<a[10]+a[11]+a[12]<<endl;
       return 0;

}



Measured memory_bytes: 3164
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
#define Priq priority_queue<int,vi,greater<int>>
#define pb push_back
#define mp make_pair
#define INF (1ll<<60)
signed main(){
  string S; cin>>S;
  int N=S.size();
  if(S[N-1]=='1'||S[0]=='0') cout<<-1<<endl;
  else{
    S.pop_back();
    string T=S;
    reverse(ALL(T));
    if(T!=S) cout<<-1<<endl;
    else{
      int cnt=1,memo=1;
      rep(i,0,N-1){
        if(S[i]=='1'){
          rep(j,0,cnt){
            int X=i+2-j;
            cout<<memo<<" "<<X<<endl;
          }
          cnt=1;
          memo=i+2;
        }
        else cnt++;
      }
    }
  }
  }



Measured memory_bytes: 1664
#include <iostream>
using namespace std;
int dp[200000],n,q,a,b,c;
void BITadd(int a,int b){
    while(a>0){
        dp[a]+=b;
        a-=a&(-a);
    }
    return ;
}
int BITget(int a){
    int tot=0;
    while(a<=200000){
        tot+=dp[a];
        a+=a&(-a);
    }
    return tot;
}
int main(void){
    cin>>n>>q;
    while(q--){
        cin>>a;
        if(a==0){
            cin>>a>>b>>c;
            BITadd(b,c);
            BITadd(a-1,-c);
        }
        else{
            cin>>a;
            cout<<BITget(a)<<endl;
        }
    }
}



Measured memory_bytes: 3476
fn main() {
    loop {
        let n = {
            let mut s = String::new();
            std::io::stdin().read_line(&mut s).unwrap();
            #[allow(deprecated)]
            let s = s.trim_right().to_owned();
            s.parse::<usize>().unwrap()
        };
        if n == 0 {
            std::process::exit(0);
        }
        let mut a = (0..n)
            .map(|_| {
                let mut s = String::new();
                std::io::stdin().read_line(&mut s).unwrap();
                #[allow(deprecated)]
                let s = s.trim_right().to_owned();
                s.parse::<u32>().unwrap()
            })
            .collect::<Vec<_>>();
        a.sort();
        println!("{}", a[1..a.len() - 1].iter().sum::<u32>() / (n - 2) as u32);
    }
}



Measured memory_bytes: 5048
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<vector<int> > Graph;
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; }
 
int n,a,b,c,d;
string s;
 
bool solve(int f,int t){
    int now = f;
    while(now!=t){
        if(s[now+1]!='#')now++;
        else if(s[now+2]!='#')now+=2;
        else return false;
    }
    return true;
}
int main(){
    cin >> n >> a >> b >> c >> d;
    a--;b--;c--;d--;
    cin >> s;
    bool ans = false;
    //追い抜きなしのパターン
    if(solve(b,d)){
        s[d]='#';
        if(solve(a,c))ans=true;
        s[d]='.';
    }
    //追い抜きありのパターン
    if(solve(b,d)){
        bool nx=false;
        for(int i = b-1;i<d-1;i++){
            if(s[i]=='.'&&s[i+1]=='.'&&s[i+2]=='.')nx=true;
        }
        if(nx){
            solve(a,c);
            s[c]='#';
            if(solve(b,d))ans=true;
        }
    }
    if(ans)cout << "Yes" << endl;
    else cout << "No" << endl;
 
    return 0;
}


Measured memory_bytes: 768
N, K = map(int, input().split())
A = list(map(int, input().split()))

S = []
for l in range(0, N):
  temp = 0
  for r in range(l, N):
    temp += A[r]
    S.append(temp)

max_s = max(S)
n = max_s.bit_length()
S_temp = [S, []]
s_idx = 0
for i in range(n-1, -1, -1):
  c = 0
  for s in S_temp[s_idx]:
    if (s >> i) & 1:
      S_temp[s_idx-1].append(s)
      c += 1
  if c == K:
    ans = S_temp[s_idx-1][0]
    for _s in S_temp[s_idx-1]:
      ans &= _s
    print(ans)
    quit()
  if c > K:
    S_temp[s_idx] = []
    s_idx = not s_idx
  else:
    S_temp[s_idx-1] = []

ans = S_temp[s_idx][0]
for _s in S_temp[s_idx][:K]:
  ans &= _s

print(ans)

Measured memory_bytes: 65788
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

template<u32 M = 1000000007>
struct modint{
    u32 val;
    modint(): val(0){}
    template<typename T>
    modint(T t){t %= (T)M; if(t < 0) t += (T)M; val = t;}

    modint pow(ll k) const {
        modint res(1), x(val);
        while(k){
            if(k&1) res *= x;
            x *= x;
            k >>= 1;
        }
        return res;
    }
    template<typename T>
    modint& operator=(T t){t %= (T)M; if(t < 0) t += (T)M; val = t; return *this;}
    modint inv() const {return pow(M-2);}
    modint& operator+=(modint a){val += a.val; if(val >= M) val -= M; return *this;}
    modint& operator-=(modint a){if(val < a.val) val += M-a.val; else val -= a.val; return *this;}
    modint& operator*=(modint a){val = (u64)val*a.val%M; return *this;}
    modint& operator/=(modint a){return (*this) *= a.inv();}
    modint operator+(modint a) const {return modint(val) +=a;}
    modint operator-(modint a) const {return modint(val) -=a;}
    modint operator*(modint a) const {return modint(val) *=a;}
    modint operator/(modint a) const {return modint(val) /=a;}
    modint operator-(){return modint(M-val);}
    bool operator==(const modint a) const {return val == a.val;}
    bool operator!=(const modint a) const {return val != a.val;}
    bool operator<(const modint a) const {return val < a.val;}
};
using mint = modint<MOD>;

class Factorial {
    vector<mint> facts, factinv;
public:
    explicit Factorial(int n) : facts(n+1), factinv(n+1) {
        facts[0] = 1;
        for (int i = 1; i < n+1; ++i) facts[i] = facts[i-1] * mint(i);
        factinv[n] = facts[n].inv();
        for (int i = n-1; i >= 0; --i) factinv[i] = factinv[i+1] * mint(i+1);
    }
    mint fact(int k) const {
        if(k >= 0) return facts[k]; else return factinv[-k];
    }
    mint operator[](const int &k) const {
        if(k >= 0) return facts[k]; else return factinv[-k];
    }
    mint C(int p, int q) const {
        if(q < 0 || p < q) return 0;
        return facts[p] * factinv[q] * factinv[p-q];
    }
    mint P(int p, int q) const {
        if(q < 0 || p < q) return 0;
        return facts[p] * factinv[p-q];
    }
    mint H(int p, int q) const {
        if(p < 0 || q < 0) return 0;
        return q == 0 ? 1 : C(p+q-1, q);
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    Factorial f(m);
    mint ans = 0;
    for (int i = 0; i <= n; ++i) {
        mint val = f.C(n, i)*f.P(m, i)*f.P(m-i, n-i)*f.P(m-i, n-i);
        if(i&1) ans -= val;
        else ans += val;
    }
    cout << ans.val << "\n";
    return 0;
}

Measured memory_bytes: 7128
#include<iostream>
#include<cmath>
#include<complex>
#include<cstdlib>
#include<algorithm>
#include<functional>
using namespace std;

int main() {
    int a,b,c;
    cin>>a>>b>>c;
    cout<<a+b+c-max(max(a,b),c)<<endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <cmath>
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 INF=1001001001;
vector<pair<int64_t,int64_t>>func(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p;
}

int main() {
  int N,M;
  cin>>N>>M;
  vector<vector<int>>s(M);
  for(int i=0;i<M;i++){
    int k;
    cin>>k;
    for(int j=0;j<k;j++){
      int a;
      cin>>a;
      a--;
      s[i].push_back(a);
    }
  }
  vector<int>p(M);
  for(int i=0;i<M;i++){
    cin>>p[i];
  }
  int ans=0;
  for(int t=0;t<(1<<N);t++){
    bool ok=true;
    for(int i=0;i<M;i++){
      int cnt=0;
      for(auto v:s[i]){
        if((t>>v)&1){cnt++;}
      }
      if(cnt%2!=p[i]){ok=false;}
    }
    if(ok){ans++;}
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007; 
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

ll disy[100000],diss[100000];
vector<vector<pair<ll,ll> > > gy(100000),gs(100000);
void dy(ll s){
    multiset<pair<ll,ll> > pri;
    pri.insert(make_pair(0,s));
    pair<ll,ll> p,niko;
    ll maki;
    while(!pri.empty()){
        p=*(pri.begin());
        pri.erase(pri.begin());
        if(disy[p.second]<p.first)continue;
        maki=gy[p.second].size();
        for(int i=0;i<maki;i++){
            niko=gy[p.second][i];
            if(disy[niko.first]>disy[p.second]+niko.second){
                disy[niko.first]=disy[p.second]+niko.second;
                pri.insert(make_pair(disy[niko.first],niko.first));
            }
        }
    }
    return;
}
void ds(ll s){
    multiset<pair<ll,ll> > pri;
    pri.insert(make_pair(0,s));
    pair<ll,ll> p,niko;
    ll maki;
    while(!pri.empty()){
        p=*(pri.begin());
        pri.erase(pri.begin());
        if(diss[p.second]<p.first)continue;
        maki=gs[p.second].size();
        for(int i=0;i<maki;i++){
            niko=gs[p.second][i];
            if(diss[niko.first]>diss[p.second]+niko.second){
                diss[niko.first]=diss[p.second]+niko.second;
                pri.insert(make_pair(diss[niko.first],niko.first));
            }
        }
    }
    return;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    for(int i=0;i<100000;i++){
        disy[i]=diss[i]=1e18;
    }
    ll n,m,s,t;
    cin>>n>>m>>s>>t;
    s--;t--;
    diss[t]=0;disy[s]=0;
    ll u,v,a,b;
    for(int i=0;i<m;i++){
        cin>>u>>v>>a>>b;
        u--;v--;
        gy[u].pb(make_pair(v,a));
        gy[v].pb(make_pair(u,a));
        gs[u].pb(make_pair(v,b));
        gs[v].pb(make_pair(u,b));
    }
    dy(s);
    ds(t);
    set<ll> eri;
    set<ll> ::iterator itr;
    vector<ll> ans;
    for(int i=n-1;i>=0;i--){
        eri.insert(1000000000000000-disy[i]-diss[i]);
        itr=eri.end();
        itr--;
        ans.pb(*itr);
    }
    
    for(int i=n-1;i>=0;i--){
        cout << ans[i]<<endl;
    }
    return 0;
}


Measured memory_bytes: 23676
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
//#include<bits/stdc++.h>

int main()
{
  int N;
  cin >> N;

  long long sum = 0;
  vector<int> number;

  for (int i = 0; i <= N; i++)
  {
    if (i % 15 == 0)
      continue;
    else if (i % 5 == 0)
      continue;
    else if (i % 3 == 0)
      continue;
    else
    {
      number.push_back(i);
    }
  }

  for (int i = 0; i < number.size(); i++)
  {
    sum += number[i];
  }

  cout << sum << endl;

  return 0;
}

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

#define PI 3.1415926535897932
#define MOD 1000000007
#define INF 1e9

#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define FOR(i, start, end) for(int i = (start); i < (end); i++)
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;


void solve()
{
    int a, b; cin >> a >> b;
    if((a * b) % 2 == 1) cout << "Odd" << endl;
    else cout << "Even" << endl;
}

int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<bits/stdc++.h>
#define ll long long int
#define lld long double
#define F first
#define S second
#define f(i,a,b) for(int i=a;i<=b;i++)
#define g(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mh make_heap
#define ph push_heap
#define pq priority_queue
#define bits(x) __builtin_popcountll(x)
#define op(x) cout<<"Case #"<<x<<": "
#define op1(x) cout<<"Scenario #"<<x<<": "
#define endl "\n"
using namespace std;
const ll mod = 1000000007;
const ll INF = 1e18;
const int N = 20;


/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define policy tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
*/


void solve(int t)
{


	ll x;
	cin >> x;
	if (x >= 30)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}


}

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



	int t = 1;
	//cin >> t;


	for (int i = 1; i <= t; i++)
	{
		solve(i);

	}
}

Measured memory_bytes: 3580
(h,w),*a=[map(int,o.split())for o in open(0)]
B=[];l=[]
for y in range(h):
 *A,=a[y];x=0
 for x in range(1,w):
  if A[x-1]%2:l+=(y+1,x,y+1,x+1),;A[x]+=1
 B+=A[x],
 if y and B[-2]%2:l+=(y,w,y+1,w),;B[y]+=1
print(len(l))
for a in l:print(*a)

Measured memory_bytes: 25588
from collections import deque
from collections import defaultdict
def main():
    n = int(input())
    # 隣接リスト 距離
    dc = defaultdict(list)
    for _ in range(n-1):
        a,b,c = map(int,input().split())
        dc[a].append([b,c])
        dc[b].append([a,c])


    que = deque([1])
    # 調べたか判定
    visited = [0]*(n+1)
    visited[0] = 1
    visited[1] = 1

    ans = [1]*(n+1)
    while len(que)>0:
        now = que.popleft()
        for ls in dc[now]:
            next_,_ = ls
            if visited[ls[0]]==0:
                if ls[1]%2==0:
                    ans[next_] = ans[now]
                else:
                    ans[next_] = -ans[now]
                
                visited[ls[0]]=1
                que.append(ls[0])
            else:
                pass
        
                    
    for i in range(1,n+1):
        if ans[i]==1:
            print(1)
        else:
            print(0)
if __name__ == "__main__":
    main()


    
  



Measured memory_bytes: 95832
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

template<typename T>
vector<T> gen_v(size_t a) { return vector<T>(a); }
template<typename T, typename ...Ts>
auto gen_v(size_t a, Ts... ts) { return vector<decltype(gen_v<T>(ts...))>(a, gen_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); }

template<class T, class ...Tail>
void tiedSort(vector<T> &a, vector<Tail>&... tail) {
	int n = a.size();
	using S = tuple<T, Tail...>;
	vector<S> s(n);
	for (int i = 0; i < n; i++)
		s[i] = make_tuple(a[i], tail[i]...);
	sort(s.begin(), s.end());
	for (int i = 0; i < n; i++)
		tie(a[i], tail[i]...) = s[i];
}

int solve(int N, int T, vector<int> A, vector<int> B) {
	tiedSort(A, B);
	int M = T + *max_element(all(A)) + 1;
	auto dp = gen_v<int>(M);
	fill_v(dp, -1);
	dp[0] = 0;

	rep(i, 0, N) {
		rrep(j, 0, T) {
			if (dp[j] == -1)continue;
			chmax(dp[j + A[i]], dp[j] + B[i]);
		}
	}
	return *max_element(all(dp));
}

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

	int N, T; cin >> N >> T;
	vector<int> A(N), B(N); rep(i, 0, N) {
		cin >> A[i] >> B[i];
	}

	cout << solve(N, T, A, B) << endl;

	return 0;
}

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

int main(){
  int n;
  cin>>n;
  int a[n];
  int b[n-1];
  for(int i=1;i<n;i++){
    cin>>b[i];
  }
  a[1]=b[1];
  a[n]=b[n-1];
  for(int i=2;i<n;i++){
    a[i]=min(b[i-1],b[i]);
  }
  int res=0;
  for(int i=1;i<=n;i++){
    res+=a[i];
  }
  cout<<res<<endl;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
AB = []

for _ in range(N):
    Ai, Bi = map(int, input().split())
    AB.append((Ai, Bi))

AB = sorted(AB)
ans = 0
num = 0

for item in AB:
    if M - num >= item[1]:
        ans += item[0] * item[1]
        num += item[1]
    else:
        buy_num = M - num
        ans += item[0] * buy_num
        break
print(ans)


Measured memory_bytes: 17788
// AtCoder ABC120: C - Unification
// 2019.9.9 bal4u
// Template for Online Contest

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

typedef long long ll;

#define gc() getchar()
#define pc(c) putchar(c)

int in() {  // 整数の入力
	int n = 0, c = gc();
	if (c == '-') {	c = gc();
		do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
		return -n;
	}
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

ll inL() {  // long long 整数の入力
	ll n = 0; int c = gc();
	if (c == '-') {	c = gc();
		do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
		return -n;
	}
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

void out(int n) { // 整数の表示
	int i; char b[30];
	if (!n) pc('0');
	else {
		if (n < 0) pc('-'), n = -n;
		i = 0; while (n) b[i++] = n % 10 + '0', n /= 10;
		while (i--) pc(b[i]);
	}
	pc('\n');
}

void outL(ll n) { // 整数の表示
	int i; char b[30];
	if (!n) pc('0');
	else {
		if (n < 0) pc('-'), n = -n;
		i = 0; while (n) b[i++] = n % 10 + '0', n /= 10;
		while (i--) pc(b[i]);
	}
	pc('\n');
}

int ins(char *s) { // 文字列の入力
	char *p = s--; int c;
	do c = gc(), *++s = c & 0xf;
	while (c > ' ');
	*s = 0;
	return s - p;
}

void outs(char *s) {  // 文字列の表示
	while (*s) pc(*s++);
}

#define MIN(a,b)  ((a)<=(b)?(a):(b))
#define MAX(a,b)  ((a)>=(b)?(a):(b))
#define ABS(a)    ((a)>=0?(a):-(a))
inline static int chmax(int *a, int b) { if (*a < b) *a = b; }
inline static ll  chmaxL(ll *a, int b) { if (*a < b) *a = b; }
inline static int chmin(int *a, int b) { if (*a > b) *a = b; }
inline static ll  chminL(ll *a, int b) { if (*a > b) *a = b; }

int cmp_int(const void *u, const void *v) { return *(int *)u - *(int *)v; }

int N;
char S[100005];
char q[100005]; int top;
int main()
{
	int i, j, ans;

	N = ins(S);
	ans = 0, top = 0;
	for (i = 0; i < N; i++) {
		if (top == 0) q[top++] = S[i];
		else {
			if (q[top-1] + S[i] == 1) top--, ans += 2;
			else q[top++] = S[i];
		}
	}
	out(ans);
	return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T> ostream& operator<<(ostream& s,const multiset<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double EPS=1e-10;
const double PI=acos(-1);

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    int n;
    cin>>n;
    vector<ll> a(n+1),sum(n+1,0);
    rep(i,n+1){
        cin>>a[i];
        if(i) sum[i]=sum[i-1]+a[i];
        else sum[i]=a[i];
    }
    ll now=1;
    ll ans=0;
    rep(i,n+1){
        if(now<a[i]){
            cout<<-1<<endl;
            return 0;
        }
        if(i!=n && now==a[i]){
            cout<<-1<<endl;
            return 0;
        }
        ans+=now;
        ll ret=now-a[i];//下に行く頂点の数
        ll ne=sum[n]-sum[i];//i+1以降にある葉の数
        if(ret>ne){
            cout<<-1<<endl;
            return 0;
        }
        //ne-ret個葉を増やす必要あり
        now=min(ret+ne-ret,2*ret);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 4780
#include <iostream>
using namespace std;
int main(int argc, char* argv[])
{
    int a, b, c;
    int n=0;
    cin >> a >> b >> c;

    for (int i = 1; i <= c; i++)
    {
        if(c%i==0 && i>=a && i<=b) n++;
    }
    cout << n << endl;
    return 0;
}




Measured memory_bytes: 3108
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
using namespace std;

int main(void) {
    int n;
    cin >> n;
    for (int i=1;i<=n;i++){
        if (i%3==0){
            cout << " " << i;
        } else {
            int x = i;
            for (int f = 0;!f;) {
                if (x%10==3){
                    cout << " " << i;
                    f = 1;
                }
                if (x < 1) f = 1;
                x /= 10;
            }
        }
    }
    cout << endl;
    return 0;
}

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

int main(){
	/*
		0
	3	1	2	4
		5
	*/
	int dice[6];
	for(int i = 0; i < 6; i++) cin >> dice[i];
	string input;
	cin >> input;
	for(int i = 0; i < input.length(); i++){
		if( input[i] == 'N'){
			int tmp = dice[0];
			dice[0] = dice[1];
			dice[1] = dice[5];
			dice[5] = dice[4];
			dice[4] = tmp;
		}
		if( input[i] == 'S'){
			int tmp = dice[0];
			dice[0] = dice[4];
			dice[4] = dice[5];
			dice[5] = dice[1];
			dice[1] = tmp;
		}
		if( input[i] == 'E'){
			int tmp = dice[0];
			dice[0] = dice[3];
			dice[3] = dice[5];
			dice[5] = dice[2];
			dice[2] = tmp;
		}
		if( input[i] == 'W'){
			int tmp = dice[0];
			dice[0] = dice[2];
			dice[2] = dice[5];
			dice[5] = dice[3];
			dice[3] = tmp;
		}
	}
	cout << dice[0] << endl;
	return 0;
}


Measured memory_bytes: 3176