akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORR(i, a, b) for(int i = (a); i > (b); --i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x)                                                              \
    for(auto &youso_ : (x)) cin >> youso_
#define mp make_pair
#define bitcnt __builtin_popcount
#define All(a) (a).begin(), (a).end()
template <typename T = long long> inline T IN() {
    T x;
    cin >> x;
    return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
    cin >> head;
    CIN(move(tail)...);
}
#define CINT(...)                                                              \
    int __VA_ARGS__;                                                           \
    CIN(__VA_ARGS__)
#define LCIN(...)                                                              \
    ll __VA_ARGS__;                                                            \
    CIN(__VA_ARGS__)
#define SCIN(...)                                                              \
    string __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"

typedef long long ll;
typedef unsigned long long ul;
typedef vector<int> V;
typedef vector<ll> VL;
typedef pair<int, int> Pair;
typedef pair<ll, ll> PL;
typedef priority_queue<int> PQ;
typedef priority_queue<int, V, greater<int>> PQG;

const int INF = 1e9;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
const ll LINF = 1e18;

ll H, W;
vector<string> board;
vector<VL> dist;
ll dw[4] = {1, -1, 0, 0};
ll dh[4] = {0, 0, 1, -1};

int main() {
    cin >> H >> W;
    board.assign(H + 2, string(W + 2, '#'));
    dist.assign(H + 2, VL(W + 2, LINF));
    ll num = 0;
    FOR(i, 1, H + 1) {
        SCIN(s);
        board[i] = "#" + s + "#";
        num += count(All(board[i]), '#') - 2;
    }
    queue<PL> q;
    q.push({1, 1});
    dist[1][1] = 1;
    while(!q.empty()) {
        PL now = q.front();
        q.pop();
        if(now.first == H && now.second == W) {
            cout << H * W - dist[H][W] - num << "\n";
            return 0;
        }
        REP(i, 4) {
            ll nh = now.first + dh[i];
            ll nw = now.second + dw[i];
            if(dist[nh][nw] == LINF && board[nh][nw] == '.') {
                q.push({nh, nw});
                dist[nh][nw] = dist[now.first][now.second] + 1;
            }
        }
    }
    cout << -1 << "\n";
}

Measured memory_bytes: 256
main = do
    input <- getContents
    let (_:xss) = map words $ lines input :: [[String]]
    mapM_ putStrLn (map ans xss)

ans (x:y:z:_)
    | a*a == b*b + c*c = "YES"
    | b*b == c*c + a*a = "YES"
    | c*c == a*a + b*b = "YES"
    | otherwise = "NO"
    where a = read x
          b = read y
          c = read z

Measured memory_bytes: 4100
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <bits/stdc++.h>
using namespace std;

class AACOrWA {
 public:
  void solveOne(std::istream &in, std::ostream &out) {
    int a, b;
    in >> a >> b;
    out << (a == b ? "Yes" : "No") << '\n';
  }
  void solve(std::istream &in, std::ostream &out) {
    int nt = 1;
    for (int i = 0; i < nt; ++i)
      solveOne(in, out);
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  AACOrWA solver;
  std::istream &in(std::cin);
  std::ostream &out(std::cout);
  solver.solve(in, out);
  return 0;
}

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

#define M 1000000007
#define MM 998244353 
#define ll long long 
#define pb push_back
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define memf(a) memset(a,false,sizeof(a))
#define all(v) v.begin(),v.end()
#define sz(a) (ll)a.size()
#define F first
#define S second
#define PI 3.1415926536
#define INF 2000000000000000000
#define endl "\n"
#define _time_ 1.0 * clock() / CLOCKS_PER_SEC
//RNG based on mersenne_twister 
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll power(ll b,ll e,ll m)
{
	if(e==0) return 1;
	if(e&1) return b*power(b*b%m,e/2,m)%m;
	return power(b*b%m,e/2,m);
}
ll power( ll b, ll e)
{
	if(e==0) return 1;
	if(e&1) return b*power(b*b,e/2);
	return power(b*b,e/2);
}
template<typename T, typename U> static inline void amin(T &x, U y){ if(y<x) x=y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x<y) x=y; }


int _runtimeTerror_()
{
	int n;
	cin>>n;
	ll ans=0;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)
		{
			for(int k=1;k<=n;++k)
			{
				int x=__gcd(i,j);
				x=__gcd(x,k);
				ans+=x;
			}
		}
	}
	cout<<ans;
	return 0;
}

int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	#ifdef runSieve
		sieve();
	#endif
	#ifdef NCR
		initialize();
	#endif
	int TESTS=1;
	//cin>>TESTS;
	while(TESTS--)
		_runtimeTerror_();
	cerr<<"\n"<<_time_;
	return 0;
}


Measured memory_bytes: 3808
n,m = map(int, input().split())
A = [list(map(int, input().split())) for i in range(n)]
b = [int(input()) for j in range(m)]

ans = [sum([a[i]*b[i] for i in range(len(b))]) for a in A]
for xj in ans:
    print(xj)



Measured memory_bytes: 6028
import bisect
from collections import deque

N = int(input())
a = []
for _ in range(N):
  a.append(int(input()))

LIS = deque([a[0]])
for i in range(1,N):
    if a[i] > LIS[-1]:
    	LIS[-1] = a[i]
    elif LIS[0] >= a[i]:
    	LIS.appendleft(a[i])
    else:
    	LIS[bisect.bisect_left(LIS, a[i])-1] = a[i]

print(len(LIS))


Measured memory_bytes: 8060
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define trav(x, v) for(auto &x : v)
#define all(v) v.begin(), v.end()
#define sz(v) int(v.size())
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<vi> vvi;

int main(){
	cin.tie(0);
	cin.sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	int n, a, b, c, d;
	cin >> n >> a >> b >> c >> d;
	--a, --b, --c, --d;
	string s;
	cin >> s;

	bool ans = true;
	rep(i,a,c) if(s[i]=='#' && s[i+1]=='#') ans = false;
	rep(i,b,d) if(s[i]=='#' && s[i+1]=='#') ans = false;
	bool foo = d > c;
	if(d < c) rep(i,max(1,b), min(n-1,d+1)) if(s[i-1]=='.' && s[i]=='.' && s[i+1]=='.') foo = true;
	cout << (ans && foo ? "Yes" : "No") << endl;
}


Measured memory_bytes: 592
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
int main()
{
    int a,b;
    while(~scanf("%d%d",&a,&b)){
        int ans = 0;
        for(int i=a;i<=b;i++){
            char a,b,c,d,e;
            e = i%10;
            d = (i/10)%10;
            b = (i/1000)%10;
            a = i/10000;
            if(a == e&&b == d)
                ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>

int main()
{
  int N;
  std::string S;
  std::cin >> N >> S;
  
  int count = 0;
  for (int i=0; i<N; ++i)
	if (i==0 || S[i-1] != S[i])
      count += 1;

  std::cout << count << std::endl;
  return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main(){
    int p;
    deque <int>a;
    cin>>p;
    while(p){
        p--;
        int n,i,q;
        cin>>n;
        if(n==0){
            cin>>q>>i;
            if(q==1)
            a.push_back(i);
            else
            a.push_front(i);
        }
        if(n==1){
            cin>>i;
            cout<<a[i]<<endl;
        }
        if(n==2){
        	cin>>q;
        	if(q==1)
            a.pop_back();
            else
            a.pop_front();
        }
    }
}


Measured memory_bytes: 4532
/*************************************************************************
  >         File: B.cc
  >       Author: lyyllyyl
  >         Mail: riho.yoshioka@yandex.com
  > Created Time: Sun 04 Sep 2016 08:18:12 PM CST
*************************************************************************/
#include <bits/stdc++.h>
using LL = long long;
int a[2222];
LL b[2222];

int main() {
  std::ios::sync_with_stdio(0);
  int n, x;
  std::cin >> n >> x;
  for (int i = 0; i < n; i++) {
    std::cin >> a[i];
    b[i] = a[i];
  }
  LL answer = 1LL << 60;
  for (int itr = 0; itr < n; itr++) {
    for (int i = 0; i < n; i++) b[(i + itr) % n] = std::min(b[(i + itr) % n], 1LL * a[i]);
    LL sum = 0;
    for (int i = 0; i < n; i++) sum += b[i];
    answer = std::min(answer, sum + 1LL * itr * x);
  }
  std::cout << answer << std::endl;

  return 0;
}


Measured memory_bytes: 256
n,m = map(int,input().split())
inf = 10**9+7
if n<m: n,m = m,n
if n-m > 1:
    ans = 0
else:
    ans = 1
    for i in range(2,m+1):
        ans = ans*i*i%inf
    if n == m:
        ans = ans*2%inf
    else:
        ans = ans*n%inf

print(ans)

Measured memory_bytes: 3060
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
using namespace std;

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	int m = abs(b - a);
	int n = abs(c - a);
	int o = abs(b - c);
	int s = min(m+ n,n+o);
	s = min(s, m+o);
	cout << s;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
typedef long long int ll;
using namespace std;

int main()
{

    int n,m;
    cin>>n>>m;
    vector<int> a(n);
    int sum=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }

    int cnt=0;
    for(int i=0;i<n;i++)
    {
        if(4*m*a[i]>=sum)
            cnt++;
    }

    if(cnt>=m)
        cout<<"Yes"<<endl;
    else cout<<"No"<<endl;




    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

struct Edge {
    int to, cost;
    bool operator<(const Edge& o) const {
        return cost > o.cost;
    }
};

const int MAX_V = 10000;
const int INF = 1 << 28;

int V, E;
vector<Edge> edges[MAX_V];
bool done[MAX_V];

int main() {
    cin >> V >> E;
    for (int i = 0; i < E; ++i) {
        int s, t, w;
        cin >> s >> t >> w;
        edges[s].push_back((Edge) { t, w });
        edges[t].push_back((Edge) { s, w });
    }

    int res = 0;
    priority_queue<Edge> que;
    fill(done, done + V, false);
    que.push((Edge) { 0, 0 });
    while (!que.empty()) {
        Edge e = que.top();
        que.pop();
        if (done[e.to]) { continue; }
        done[e.to] = true;
        res += e.cost;
        for (Edge e2: edges[e.to]) {
            que.push(e2);
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 7948
#include <bits/stdc++.h>
using namespace std;
int main(){
int H, W; 
cin >> H >> W; 
char A[510][510] = {}; 
char B[510][510] = {}; 
char C[510][510] = {}; 
for(int i = 0; i < H; i++){
  for(int j = 0; j < W; j++){
cin >> A[i][j]; 
if(i == 0 || (j % 2 == 0 && i < H-1) || A[i][j] == '#'){
B[i][j] = '#'; 
  }
else{
B[i][j] = '.'; 
}
if(i == H-1 || (j % 2 == 1 && i > 0) || A[i][j] == '#'){
C[i][j] = '#'; 
  }
else{
C[i][j] = '.'; 
}
}
}
for(int i = 0; i < H; i++){
  for(int j = 0; j < W; j++){
cout << B[i][j]; 
  }
cout << endl; 
}
cout << endl; 
for(int i = 0; i < H; i++){
  for(int j = 0; j < W; j++){
cout << C[i][j]; 
  }
cout << endl; 
}
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define RFOR(i,a,n) for(ll i=(ll)n-1;i >= (ll)a;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,0,n)
#define ALL(v) v.begin(), v.end()
#define bra(first,second) '(' << first << ',' << second << ')'
constexpr ll MOD = 1000000007;
//constexpr ll MOD = 998244353;
ll INF = 4001001001001001001;
long double EPS = 1e-9;
long double PI = 3.141592653589793238;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index){
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<pair<ll,ll>>>;

// MOD確認

int main(){
    /*ll S,W;
    cin >> S >> W;
    if(S <= W * 2) cout << "unsafe" << endl;
    else cout << "safe" << endl;*/
    ll A,B,C,D;
    cin >> A >> B >> C >> D;
    rep(i,1000){
        if(i % 2 == 0){
            C -= B;
        }else{
            A -= D;
        }
        if(A <= 0){
            cout << "No" << endl;
            break;
        }
        if(C <= 0){
            cout << "Yes" << endl;
            break;
        }

    }
}


Measured memory_bytes: 3632
-- ABC124 A problem
import Control.Monad

toInt :: String -> Int
toInt x = read x :: Int

getInts = do
  x <- getLine
  let y = (map$toInt)$words x
  return y

maxGain :: Int -> Int -> Int
maxGain m n =
  if m - n >= 2 then 2*m - 1
  else
    if m >= n then m + n
    else maxGain n m

main :: IO ()
main = do
  x <- getInts
  let a = head x :: Int
  let b = last x :: Int
  print (maxGain a b)

Measured memory_bytes: 508
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
	Scanner scan = new Scanner(System.in);

	//入力文字列反転
	String S = scan.next();
	StringBuffer sb = new StringBuffer(S);
	String S_r = sb.reverse().toString();

	//比較文字列反転
	String[] d_ = {"dream", "erase", "eraser", "dreamer"};
	String[] dr_ = new String[d_.length];
	for(int i = 0; i < d_.length; i++){
	    StringBuffer db = new StringBuffer(d_[i]);
	    dr_[i] = db.reverse().toString();
	}

	int bool = 1;
	for(int i = 0; i < S_r.length();){
	    int flag = -1;
	    for(int j = 0; j < dr_.length; j++){
		if(S_r.substring(i, i+dr_[j].length()).compareTo(dr_[j]) == 0){
		    i += dr_[j].length();
		    flag = 1;
		    break;
		}
	    }
	    if(flag == -1){
		bool = -1;
		break;
	    }
	}

	if(bool == 1){
	    System.out.println("YES");
	}else{
	    System.out.println("NO");
	}
    }
}
		


Measured memory_bytes: 28316
#include <iostream>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
vector<ll> a;
vector<ll> p;
 
ll f(ll n, ll x) {
    if(n==0)
        return 1;
    if(x==1)
        return 0;
    if(x <= 1 + a[n-1]) {
        return f(n-1,x-1);
    }
    if(x == a[n-1]+2) {
        return p[n-1] + 1;
    }
    return p[n-1] + 1 + f(n-1, x-2-a[n-1]);
}
 
int main() {
    ll n,x; cin >> n >> x;
    a.push_back(1);
    p.push_back(1);
    for(int i = 1; i <= n; i++) {
        a.push_back(a[i-1]*2 + 3);
        p.push_back(p[i-1]*2 + 1);
    }
 
    cout << f(n, x) << endl;
}

Measured memory_bytes: 256
N, K = map(int, input().split())

snuke = [0 for i in range(N)]

for i in range(K):
  d = int(input())
  A = list(map(int, input().split()))
  for j in A:
    snuke[j-1] += 1

ans = 0
for i in snuke:
  if i == 0:
    ans += 1
print(ans)

Measured memory_bytes: 9192
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <climits>
#include <stack>
#include <queue>
#include <set>
#include <cctype>
#include <bitset>
#include <type_traits>

#include <list>
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define YES(j) cout << (j ? "YES" : "NO") << endl;
#define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
#define yes(j) std::cout << (j ? "yes" : "no") << endl;

int main(void)
{
    int n;
    cin >> n;
    int a[n], m[n];
    int min;
    REP(i, n)
    {
        cin >> a[i];
        if (i == 0)
        {
            min = a[i];
            m[i] = min;
        }
        else
        {
            if (min > a[i])
            {
                min = a[i];
            }
            m[i] = min;
        }
    }
    int ans = 1;
    rep(i, 1, n)
    {
        if (m[i - 1] >= a[i])
            ans++;
    }
    cout << ans << endl;
}

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

int main()
{
  long long n,d,a;
  cin>>n>>d>>a;
  vector<long long> x(n);
  vector<long long> h(n);
  long long i;
  for(i=0;i<n;i++)cin>>x.at(i)>>h.at(i);
  vector<pair<long long,long long>> p(n);
  for(i=0;i<n;i++)p.at(i)=make_pair(x.at(i),h.at(i));
  sort(p.begin(),p.end());
  vector<long long> sumd(n,0);
  vector<long long> xk(n);
  for(i=0;i<n;i++)xk.at(i)=p.at(i).first;
  long long ans=0;
  for(i=0;i<n;i++)
  {
    if(i!=0)sumd.at(i)=sumd.at(i)+sumd.at(i-1);
    long long left=max((long long)0,p.at(i).second-sumd.at(i)*a);
    long long times=left/a;
    if(left%a!=0)times++;
    auto it = upper_bound(xk.begin(),xk.end(),xk.at(i)+2*d);
    sumd.at(i)+=times;
    ans+=times;
    long long ls=it-xk.begin();
    if(ls<n)sumd.at(ls)-=times;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};
int main() {
  int N,K,L;cin>>N>>K>>L;
  UnionFind A(N);
  UnionFind B(N);
  for(int I=0;I<K;I++){
    int X,Y;cin>>X>>Y;X--;Y--;
    A.merge(X,Y);
  }
  for(int I=0;I<L;I++){
    int X,Y;cin>>X>>Y;X--;Y--;
    B.merge(X,Y);
  }
      map<pair<int,int>,int> ma;
    for (int v = 0; v < N; ++v) {
        pair<int,int> p(A.root(v), B.root(v));
        ma[p]++;
    }

    for (int v = 0; v < N; ++v) {
        pair<int,int> p(A.root(v), B.root(v));
        cout << ma[p] << " ";
    }
}


Measured memory_bytes: 15960
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define dupli(a) a.erase(unique(all(a)),a.end())
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
typedef multiset<ll> S;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
vvi g(200005);
vi ans(200005);
void dfs(int i,int p){
    for(ll x:g[i])if(x!=p){
        ans[x]+=ans[i];dfs(x,i);
    }
}
void solve(){
    ll n,q;cin>>n>>q;
    rep(i,n-1){
        ll a,b;cin>>a>>b;a--;b--;
        g[a].pb(b);
        g[b].pb(a);
    }
    rep(i,q){
        ll c,d;cin>>c>>d;
        ans[c-1]+=d;
    }
    dfs(0,-1);
    rep(i,n){
        if(i)cout<<' ';
        cout<<ans[i];
    }
    cout<<endl;
}
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
}

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define PI 3.14159265358979
#define MOD 1000000007 // = 10^9 + 7

using namespace std;
using ll = long long;

// a^n % mod を計算する O(log n)
ll powmod(ll a, ll n, ll mod) {
	ll ret = 1;
	while (n > 0) {
		if (n % 2 == 1) { ret = ret * a % mod; }
		a = a * a % mod;
		n /= 2;
	}
	return ret;
}

// nCr % mod を計算する O(r)
ll combmod(ll n, ll r, ll mod) {
	ll x = 1, y = 1;
	r = min(n - r, r);
	for(ll i = 0; i < r; ++i) { x = x * (n - i) % mod; }	// 分子
	for(ll i = 1; i <= r; ++i) { y = y * i % mod; }			// 分母
	return x * powmod(y, mod - 2, mod) % mod;	// nCr = (分子) * (分母)^-1 mod M
}

void solve()
{
	ll x, y;
	cin >> x >> y;
	
	if ((x + y) % 3 != 0)
	{
		cout << 0;
		return;
	}

	if (x > 2 * y || y > 2 * x)
	{
		cout << 0;
		return;
	}

	ll a = (2 * y - x) / 3LL;
	ll b = (2 * x - y) / 3LL;

	cout << combmod(a + b, min(a, b), MOD);
}

int main()
{
	fastio;
	solve();

	return 0;
}

Measured memory_bytes: 256
import numpy as np

N, M = map(int, input().split())
ab = np.zeros((N, 2))
for i in range(N):
    ab[i,:] = list(map(int, input().split()))
ab = ab[ab[:,0].argsort(), :]

cost = 0
for i in range(N):
    M -= ab[i,1]
    cost += ab[i,0] * ab[i,1]
    if M <= 0:
        cost += ab[i,0] * M
        break

print(int(cost))


Measured memory_bytes: 16332
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

std::string S;
int couA, couB, couC;

int main()
{
	in >> S;

	for (auto c : S)
	{
		if (c == 'a') { ++couA; }
		if (c == 'b') { ++couB; }
		if (c == 'c') { ++couC; }
	}
	if (abs(couA - couB) <= 1 && abs(couB - couC) <= 1 && abs(couA - couC) <= 1)
	{
		out << "YES" << std::endl;
	}
	else { out << "NO" << std::endl; }
	return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include <cassert>
#include <cmath>
#include<cstdint>


#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<int,int>;

vector<int>bitSearch(int bit,int n){
    vector<int>S,False(1,-1);
    rep(i,n)if(bit&(1<<i))S.push_back(i);
    return S;
}

template<typename A,size_t N,typename T>
void Fill(A(&array)[N],const T &val){
    fill((T*)array,(T*)(array+N),val);
}


int main(){
    ll n, a, b;
    cin >> n >> a >> b;
    ll l = b + a * (n-1), r = a + b * (n-1);
    cout << (r - l + 1 >= 0 ? r - l + 1 : 0) << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int
main ()
{

  int y;
int a;
  int b;
  int x;

  for (y=1; y<=3000; y++)

    {
     cin >> b, cin >>a;
      if (a > b)
	{
	  x = a;
	  a = b;
	  b = x;
	}
if (a==0 && b == 0) {
    return 0;
}
      cout << a << " " << b << endl;

      
}
    }



Measured memory_bytes: 3056
use proconio::input;

fn main() {
    /*     input! {
        n: usize,
        mut plan: [(i32, i32, i32); n],  // Vec<(i32, i32, i32)>
    }
 */
    input! {
        a: u64,
        b: u64,
    }



    println!("{}",a * b);
}  

Measured memory_bytes: 2156
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<cctype>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<iomanip>
#include<sstream>
#include<vector>
#include<cstdlib>
#include<ctime>
#include<list>
#include<deque>
#include<bitset>
#include<fstream>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair<int,int >
#define iiii pair<int,pii >
#define mp make_pair
#define INF 1000000000
#define MOD 1000000007
#define rep(i,x) for(int (i)=0;(i)<(x);(i)++)
inline int getint(){
    int x=0,p=1;char c=getchar();
    while (c<=32)c=getchar();
    if(c==45)p=-p,c=getchar();
    while (c>32)x=x*10+c-48,c=getchar();
    return x*p;
}
using namespace std;
//ruogu
const ll inf=2e18;
const int N=1e5+10;
int n,a[N],b[N];
ll sumx,sumy,res,ans;
vector<pii >v;
bool flag,vis[N];
//
int main(){
	n=getint();
	rep(i,n){
		a[i]=getint();
		b[i]=getint();
		sumx+=a[i];
		sumy+=b[i];
		v.push_back(mp(a[i],i));
		v.push_back(mp(b[i],i));
	}
	sort(v.begin(),v.end());
	res=min(sumx,sumy);
	rep(i,n)vis[v[i].second]=true;
	rep(i,n)if(!vis[i])flag=true;
	rep(i,n)ans+=1ll*v[i].first;
	if(flag)res=min(res,ans);
	else{
		ll tmp=inf;
		rep(i,n){
			ll buf;
			if(v[n-1].second==i)tmp=min(tmp,1ll*max(a[i],b[i])-v[n-2].first);
			else tmp=min(tmp,1ll*max(a[i],b[i])-v[n-1].first);
		}
		res=min(res,ans+tmp);
	}
	printf("%lld\n",res);
	return 0;
}

Measured memory_bytes: 2932
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;

const int N = 5e5;
const ll  I = 1e18;
int l, n, x[N];
ll pref[N];

ll sum(int l, int r) {
	return pref[r] - pref[l];
}

ll solvep(int cp, int cm) {
	assert(cp >= 1 && cm >= 0);
	int p = min(cp, cm + 1);
	int m = min(cm, cp);
	assert(p <= m + 1);
	assert(m <= p);
	ll s = 2 * sum(cp - p, cp) + 2LL * l * m - 2 * sum(n - cm, n - cm + m);
	s -= x[cp - 1];
	return s;
}

ll solvem(int cp, int cm) {
	assert(cp >= 0 && cm >= 1);
	int p = min(cp, cm);
	int m = min(cm, cp + 1);
	assert(p <= m);
	assert(m <= p + 1);
	ll s = 2 * sum(cp - p, cp) + 2LL * l * m - 2 * sum(n - cm, n - cm + m);
	s -= l - x[n - 1 - (cm - 1)];
	return s;
}

int main() {
#ifdef LC
	assert(freopen("input.txt", "r", stdin));
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> l >> n;
	for (int i = 0; i < n; ++i) {
		cin >> x[i];
	}
	for (int i = 0; i < n; ++i) {
		pref[i + 1] = pref[i] + x[i];
	}
	ll answer = 0;
	for (int cnt = 1; cnt <= n; ++cnt) {
		answer = max(answer, solvep(cnt, n - cnt));
	}
	for (int cnt = 0; cnt < n; ++cnt) {
		answer = max(answer, solvem(cnt, n - cnt));
	}
	cout << answer << "\n";
	
	return 0;
}


Measured memory_bytes: 4480
#include <cstdio>
#include <vector>
#define MAXN 100005
using namespace std;

const int M=1e9+7;

int n,k;
vector <int> g[MAXN];

int dfs(int x,int f)
{
	if (k<g[x].size()) return 0;
	int ans=1,t=!f?k-1:k-2;
	for (auto v:g[x])
		if (v!=f)
		{
			ans=1LL*ans*t%M;
			--t;
		}
	for (auto v:g[x])
		if (v!=f) ans=1LL*ans*dfs(v,x)%M;
	return ans;
}

int main()
{
	scanf("%d %d",&n,&k);
	for (int i=1,u,v;i<n;i++)
	{
		scanf("%d %d",&u,&v);
		g[u].push_back(v);g[v].push_back(u);
	}
	printf("%d\n",1LL*k*dfs(1,0)%M);
	return 0;
}

Measured memory_bytes: 10368
#include "bits/stdc++.h"

using namespace std;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i,n) for(ll i=1;i<=(ll)(n);i++)
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define rrep1(i,n) for(ll i=(ll)(n);i>0;i--)
#define REP(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = 1e18;
const ll MOD = 1000000007;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { 1,0, -1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
//#define mp make_pair


int main() {
  int n;
  cin >> n;
  set<string> st;
  string pre = "?";
  rep (i, n) {
    string s;
    cin >> s;
    if (st.count(s)) {
      cout << "No" << endl;
      return 0;
    }
    st.insert(s);
    if (pre.back() == '?' || pre.back() == s[0]) {
      pre = s;
    }
    else {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}
  


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define pb push_back
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using vst=vector<string>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };


int main(){cout<<fixed<<setprecision(10);
		   int a,b;
           char o;
           cin>>a>>o>>b;
           if(o=='+')cout<<a+b<<endl;
           else cout<<a-b<<endl;
}

Measured memory_bytes: 3640
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <iomanip>
using namespace std;
#define INF 1e9
#define PI acos(-1)
typedef long long ll;
typedef pair<int, int> p_ii;


int main() {
	
	bool flag = false;
	string s, t;
	cin >> s >> t;

	t = t + t;

	for (int i = 0; i < t.size(); i++) {
		if (t[i] == s[0]) {
			int c = 0;
			for (int j = 0; j < s.size(); j++) {
				if (i + j > t.size())break;
				if (t[i + j] != s[j])break;
				c++;
				if (c == s.size())flag = true;
			}
		}
	}

	cout << ((flag) ? "Yes" : "No") << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int main(){
  int N, i, delta, dist = 1;
  int d[100];
  cin >> N;
  for (i = 0; i < N; i++){
    cin >> d[i];
  }
  sort(d, d+N);
  for (i = 0; i < N; i++){
    if (i < N-1){
      delta = d[i+1] - d[i];
      if (delta > 0){
        dist ++;
      }
    }
  }
  cout << dist;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()

template<class T>
static inline std::vector<T> ndvec(size_t&& n, T val) { return std::vector<T>(n, std::forward<T>(val)); }
template<class... Tail>
static inline auto ndvec(size_t&& n, Tail&&... tail) {
  return std::vector<decltype(ndvec(std::forward<Tail>(tail)...))>(n, ndvec(std::forward<Tail>(tail)...));
}
template<class Cond> struct chain {
  Cond cond; chain(Cond cond) : cond(cond) {}
  template<class T> bool operator()(T& a, const T& b) const { if(cond(a, b)) { a = b; return true; } return false; }
};
template<class Cond> chain<Cond> make_chain(Cond cond) { return chain<Cond>(cond); }

pair<i64, i64> input() {
  string s;
  cin >> s;
  i64 N = s.size();
  if(N - 2 >= 0 && s[s.size() - 2] == '.') {
    return { (i64)std::stoi(s.substr(0, s.size() - 2).c_str()) * 10 + (i64)(s[s.size() - 1] - '0'), 10 };
  }
  else if(N - 3 >= 0 && s[N - 3] == '.') {
    return { (i64)std::stoi(s.substr(0, s.size() - 3).c_str()) * 100 + (i64)(s[s.size() - 2] - '0') * 10 + (i64)(s[s.size() - 1] - '0'), 100 };
  }
  else {
    return { (i64)(std::stoi(s.c_str())), 1 };
  }
}

int main() {
  i64 a;
  cin >> a;
  auto p = input();
  i64 c = a * p.first;
  c /= p.second;
  cout << c << endl;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define _abs(x)((x) < 0 ? (x) * -1 : (x))
#define _max(x, y)(max(0, max((x), (y))))
#define _min(x, y)(max(0, min((x), (y))))

bool comp(const pair<ll, ll> &a, const pair<ll, ll> &b) {
    return a.first < b.first;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    //freopen("debug.txt", "w", stderr);

    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n, k;
    ll a, b;

    cin >> n >> k;

    vector<pair<ll, ll> > v;

    ll i, j = 0;

    for (i = 0; i < n; i++) {
        cin >> a >> b;

        v.push_back(make_pair(a, b));
    }

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

    for (i = 0; i < n; i++) {
        j += v[i].second;

        if (k <= j) {
            cout << v[i].first << endl;

            break;
        }
    }

    return 0;
}


Measured memory_bytes: 2420
#include <bits/stdc++.h>
 
using namespace std;
 
#define rep(i, n) for(int64 i = 0; i < (int64)(n); i++)
 
using int64 = long long;
const int64 INF = 1LL << 60;
 
int main()
{
  int N, A, B;
  cin >> N >> A >> B;
  int ret = 0;
  for(int i = 1; i <= N; i++) {
    string s = to_string(i);
    int sum = 0;
    for(auto &j : s) sum += j - '0';
    if(A <= sum && sum <= B) ret += i;
  }
 
  cout << ret << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep_1(i,n) for(int (i)=0;(i)<=(n);(i)++)
#define rep_2(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main(){
    int n,m;cin>>n>>m;
    vector<bool> AC(n);
    vector<int> WA(n);

    int ac=0,wa=0;
    for(int i = 0;i<m;i++){
        int p;
        string m;
        cin >>p>>m;
        if(AC[p]) continue;
        if(m == "AC"){
            AC[p] = true;
            wa+=WA[p];
            ac++;
        }else{
            WA[p]++;
        }
    }

    cout << ac << " " << wa << endl;

}


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

string s;
int ans, cnt;
bool played;

int main()
{
    cin >> s;
    int n = s.size();
    do{
        played = false;
        for(int i = 2; i < n; i++){
            if(s[i - 2] != '*'){
                if(s[i - 2] != s[i]){
                    s[i - 1] = '*';
                    ans++;
                    played = true;
                }
            }
        }
        string a;
        if(played){
            for(int i = 0; i < n; i++){
                if(s[i] != '*'){
                    a += s[i];
                }
            }
        }
        s = a;
        n = s.size();
    } while(played);
    if(ans % 2){
        printf("First\n");
    }
    else {
        printf("Second\n");
    }


    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define pi 3.1415926535897932384626
using namespace std;
      
struct P{
  long long x, y;
  bool operator < (const P &a )const{
    //if(x!=a.x)
    return y<a.y;
  };
};

int a,b,c,d,i,k,n,m,e,dx[10]={1,0,-1,0,1,1,-1,-1},dy[10]={0,1,0,-1,1,-1,1,-1};
long long o[100101];
long long l[100101];
int j[1];


long long x,y,z,mod=1000000007;
//string r;
char r[22];

P u[102221];
queue<int> q;
stack<int> s;
//set<P> s;
map<int,int> p;

vector<int> v;

bool as(P a,P b)
{
  //if(a.x!=b.x)
  return a.x<b.x;
  //return a.z<b.z;
}

int main()
{
  scanf("%d %lld",&a,&x);
  for(int t=1;t<=a;t++)
  {
    long long n,m;
    scanf("%lld %lld",&m,&n);
    u[t]={n,m};
  }
  for(int t=1;t<=a;t++)
  {
    z+=u[t].x;
    y=max(y,z-u[t].y);
    o[t]=max(o[t-1],z-u[t].y);
  }
  z=0;
  for(int t=a;t;t--)
  {
    z+=u[t].x;
    y=max(max(y,z-(x-u[t].y)*2+o[t-1]),z-(x-u[t].y));
    l[t]=max(l[t+1],z-(x-u[t].y));
  }
  z=0;
  for(int t=1;t<=a;t++)
  {
    z+=u[t].x;
    y=max(y,z-u[t].y*2+l[t+1]);
    
  }
  printf("%lld",y);
}
//0
//13
//18



Measured memory_bytes: 3328
#include<stdio.h>
#include<string.h>
#define l 100005


typedef struct pp{
  char name[100];
  int t;
}P;

P Q[l];
int head,tail,n;

void enqueue(P x){
  Q[tail] = x;
  tail =(tail +1)%l;
}

P dequeue(){
  P x = Q[head];
  head = (head + 1) %l;
  return x;
}

int min(int a, int b){
  return a<b ? a : b ;
}

int main(){

  int el = 0;
  int c,i,q;
  P u;

  scanf("%d%d",&n,&q);

  for(i= 1;i<=n;i++){
    scanf("%s",Q[i].name);
    scanf("%d",&Q[i].t);
  }

  head = 1;
  tail = n + 1;

  while(head != tail){
    u = dequeue();
    c = min(q,u.t);
    u.t -=c;
    el += c;

    if(u.t>0){
      enqueue(u);
    }
    else{
   printf("%s %d\n",u.name,el);
    }
  }

  return 0;

}



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

#ifdef LOCAL
#include "dump.hpp"
#else
#define dump(...)
#define dumpv(...)
#endif

#define rep(i, n) for (int i = 0; i < (n); i++)
#define mins(x, y) (x = min(x, y))
#define maxs(x, y) (x = max(x, y))
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using P = pair<int, int>;
const int MOD = 1e9 + 7;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;

void solve() {
  int a, b, c, k;
  cin >> a >> b >> c >> k;
  int ans = false;
  rep(ia, 8) rep(ib, 8) rep(ic, 8) {
    if (ia + ib + ic == k) {
      dump(ia, ib, ic);
      if ((a << ia) < (b << ib) && (b << ib) < (c << ic)) {
        ans = true;
        break;
      }
    }
  }
  cout << (ans ? "Yes" : "No" ) << endl;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  // freopen("temp.1", "r", stdin);
  solve();
  return 0;
}

Measured memory_bytes: 3648
import sys

H, N = map(int, input().split())
A = [0] * N
B = [0] * N

for i in range(N):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    A[i] = a
    B[i] = b

max_A = max(A)
INF = 10**18
dp = [INF] * (H + max_A)
dp[0] = 0

for i in range(H):
    for j in range(N):
        dp[i + A[j]] = min(dp[i] + B[j], dp[i + A[j]])

print(min(dp[H:H + max_A]))


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

using namespace std;

using LL = long long;
const int INF = (int)1e9 + 7;
const int NS = (int)2e5 + 4;
int N;
struct Data{
    int x, y, num;
    bool operator<(const Data&r)const{
        return x < r.x;
    }
}arr[NS];
struct dsu{
    vector < int > pr, rk;
    int N;
    dsu(){}
    dsu(int n):N(n){
        pr.resize(N), rk.resize(N);
        for(int i = 0; i < N; ++i) pr[i] = i, rk[i] = 1;
    }
    inline int get(int x){
        return x == pr[x] ? x : pr[x] = get(pr[x]);
    }
    inline bool unite(int x, int y){
        x = get(x), y = get(y);
        if(x != y){
            if(rk[x] < rk[y]) swap(x, y);
            pr[y] = x, rk[x] += rk[y];
            return true;
        }
        return false;
    }
}group(NS);
multiset < pair < int, int > > st;
multiset < pair < int, int > >::iterator p;
int ans[NS];

int main(){
    scanf("%d", &N);
    for(int i = 1; i <= N; ++i){
        scanf("%d %d", &arr[i].x, &arr[i].y);
        arr[i].num = i;
    }
    sort(arr + 1, arr + N + 1);
    for(int i = 1; i <= N; ++i){
        int low = arr[i].y;
        for(p = st.begin(); p != st.end();){
            if(p->first > arr[i].y){
                break;
            }
            group.unite(p->second, i);
            low = min(low, p->first);
            st.erase(p++);
        }
        st.insert(make_pair(low, i));
    }
    for(int i = 1; i <= N; ++i){
        ans[arr[i].num] = group.rk[group.get(i)];
    }
    for(int i = 1; i <= N; ++i){
        printf("%d\n", ans[i]);
    }
    return 0;
}


Measured memory_bytes: 12668
import java.util.Scanner;

class Main {
    private static boolean[] calcPrimeTable(int n) {
        boolean[] table = new boolean[n + 1];
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (!table[i]) {
                for (int j = i + i; j <= n; j += i) {
                    table[j] = true;
                }
            }
        }
        return table;
    }

    private static void solve() {
        boolean[] table = calcPrimeTable(1 << 15);
        Scanner scanner = new Scanner(System.in);
        while (true) {
            int n = scanner.nextInt();
            int counter = 0;
            if (n == 0) {
                break;
            }
            for (int i = 2; i <= n / 2; i++) {
                if (!table[i] && !table[n - i]) {
                    counter++;
                }
            }
            System.out.println(counter);
        }
    }

    public static void main(String... args) {
        solve();
    }
}

Measured memory_bytes: 12000
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <cmath>
#include <climits>
#include <unordered_map>
using namespace std;

int main() {

long long int a,b,c,d;
cin>>a>>b>>c>>d;

long long int val=b*d;
if (b*c > val) val = b*c;
if (a*c > val) val = a*c;
if (a*d > val) val = a*d;

cout<< val<<endl;





return 0;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(int i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(int i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define uniq(x) (x).erase(unique((x).begin(), (x).end()), (x).end())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n, cnt = 0;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    
    rep(i, n) {
        if (a[i] % 2 == 1) {
            cnt++;
        }
    }
    
    cout << (((cnt % 2) == 0) ? "YES" : "NO") << endl;
    return 0;
}

Measured memory_bytes: 640
n, w = map(int, input().split())
dp = [0] * (w + 1)
for _ in range(n):
    wi, vi = map(int, input().split())
    for i in range(w, wi - 1, -1):
        dp[i] = max(dp[i], dp[i-wi] + vi)
print(dp[w])

Measured memory_bytes: 66740
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <random>
#include <queue>
#include <stack>
#include <bitset>
#include <cassert>
#define int long long
#define double long double
#define rep(i,n) for(int i=0;i<n;i++)
#define srep(i,n,m) for(int i=n;i<m;i++)
#define elif else if
#define pi 3.141592653589793
#define prique priority_queue
constexpr auto mod=1000000007;
using namespace std;
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a*b/gcd(a,b);
}
bool prime(int n){
    int cnt=0;
    for(int i=1;i<=sqrt(n);i++){
        if(n%1==0)cnt++;
    }
    if(cnt!=1) return false;
    else return n!=1;
}
struct UnionFind{
    vector<int> r;
    UnionFind(int N){
        r=vector<int>(N,-1);
    }
    int root(int x){
        if(r[x]<0) return x;
        return r[x]=root(r[x]);
    }
    bool unite(int x,int y){
        x=root(x);
        y=root(y);
        if(x==y) return false;
        if(r[x]>r[y]) swap(x,y);
        r[x]+=r[y];
        r[y]=x;
        return true;
    }
    int size(int x){
        return -r[root(x)];
    }
};
vector<int> v;
int n,m,cnt=0,ans=0,aa[220000];
pair<int,int> pp[220000];
string s,ss[220000];
queue<int> que;
signed main(){
    cin>>n;
    rep(i,n){
        cin>>pp[i].first>>pp[i].second;
        if(pp[i].first==pp[i].second){
            cnt++;
        }else{
            cnt=0;
        }
        if(cnt==3){
            cout<<"Yes";
            return 0;
        }
    }
    cout<<"No";
}

Measured memory_bytes: 10600
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
const long long mod = 1e9+7;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
const int ddx[4] = {1,1,-1, -1};
const int ddy[4] = {1,-1,-1,1};
//////////////////////////////////

bool isPalindrome(string s) {
  for(int i=0; i<s.size(); i++) {
    if (s[i] != s[s.size()-1-i]) return false;
  }
  return true;
}

int main(){
  string s; cin >> s;
  string s1 = s.substr(0, s.size()/2);
  string s2 = s.substr(s.size()/2+1, s.size()/2);
  if (isPalindrome(s) && isPalindrome(s1) && isPalindrome(s2) ) cout << "Yes" << endl;
  else cout << "No" << endl;
}

// EOF


Measured memory_bytes: 256
#include <iostream>

using namespace std;
int l[110],d[110];
int main(){
	int i,n,cnt = 0,x;
	cin >> n >> x;
	d[0] = 0;
	for(i=0;i<n;i++){
		cin >> l[i];
		d[i+1] = d[i] + l[i];
	}
	for(i=0;i<=n;i++){
		if(d[i]<=x) cnt++;
	}
	cout << cnt << endl;
}

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

using namespace std;

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;

#ifdef WIN32
    #define LLD "%I64d"
#else
    #define LLD "%lld"
#endif

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

int should[50], can[50];
int n;

int main()
{
    scanf("%d", &n);
    int ttxor = 0;
    for (int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        ttxor ^= x;
        int cur = 0;
        while (x % 2 == 0)
        {
            cur++;
            x /= 2;
        }
        can[cur] = true;
    }
    for (int i = 0; i < 40; i++)
    {
        should[i] = (ttxor & 1);
        ttxor /= 2;
    }
    int curxor = 0;
    int ans = 0;
    for (int i = 39; i >= 0; i--) if (should[i] != curxor)
    {
        if (!can[i])
        {
            printf("-1\n");
            return 0;
        }
        ans++;
        curxor ^= 1;
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
    int room[4][3][10];  // 4 buildings, 3 floors, 10 rooms
    int trials;          // number of trials
    int bi, fi, ri, ni;  // inputs for building, floor, room and number
    // init rooms
    for(int b=0; b<4; b++){
        for(int f=0; f<3; f++){
            for(int r=0; r<10; r++){
                room[b][f][r] = 0;
            }
        }
    }
    // processing inputs
    cin >> trials;
    while(trials--){
        cin >> bi >> fi >> ri >> ni;
        room[bi-1][fi-1][ri-1] += ni;
    }

    // render array into sketch
    for(int b=0; b<4; b++){
        for(int f=0; f<3; f++){
            for(int r=0; r<10; r++){
                cout<<" "<<room[b][f][r]<<flush;
            }
            cout<<endl;
        }
        if(b!=3)cout<<"####################"<<endl;
    }

    return 0;
}


Measured memory_bytes: 3100