akhauriyash/Code-Regression huggingface dataset:
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main(){
    input!{
        n: usize,
        a: [i32; n],
    }

    let mut ans = 0;

    let mut i = 0;
    while i < n {
        ans += a[i] % 2;
        i += 2;
    }

    println!("{}", ans);
}

Measured memory_bytes: 2176
#include <stdio.h>

int main(){
  int H,W;
  int i;

  scanf("%d%d",&H,&W);
  char C[H][W+1];

  for(i=0;i<H;i++)scanf("%s",C[i]);
  for(i=0;i<H*2;i++)printf("%s\n",C[i/2]);

  return 0;
}

Measured memory_bytes: 128
#include <stdio.h>

int main()
{

  int S[10000],T[500],checked[500],n,q,i,j,number_of_coresspond=0;

  scanf("%d",&n);
  for(i = 0 ; i< n ; i++)scanf("%d",&S[i]);
  scanf("%d",&q);
  for(i = 0 ; i < q; i++)scanf("%d",&T[i]);

  for(i = 0; i<q ; i++)
    {
      for(j = 0 ; j <n ; j++)
        {
          if(T[i] == S[j])
            {
              number_of_coresspond++;
              break;
            }
          
        }

    }
  printf("%d\n",number_of_coresspond);
    
  
}


Measured memory_bytes: 2144
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define VSORT(v) sort(v.begin(), v.end());
#define VREV(v) reverse(v.begin(), v.end());
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;
using vll = vector<ll>;
using vdouble = vector<double>;
using vstr = vector<string>;
typedef pair<int,int> P;
int dx[4] = {1, 0, -1, 0},dy[4] = {0, 1, 0, -1};
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
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 ll INF = 1LL << 60;
const ll mod = 1000000007;

int main(){
	//入力
    ll A,B; cin>>A>>B;
	for(ll i=1; i<10100; i++){
		ll a=i/12.5,b=i/10;
		if(a==A&&b==B){
			cout<<i<<endl;
			return 0;
		}
	}
	cout<<-1<<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int n = sc.nextInt();
			if (n == 0) {
				break;
			}
			int[] num = new int[7];
			for(int i=0;i<n;i++) {
				int x = sc.nextInt();
				num[x >= 60 ? 6 : x / 10]++;
			}
			for(int i=0;i<7;i++) {
				System.out.println(num[i]);
			}
		}
	}

}

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

//{{{
/********************************************************************/
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef queue<int> qi;
typedef stack<int> si;
typedef deque<int> dqi;

#define reps(i, a, b) for (int i = a; i < b; ++i)
#define rep(i, n) reps(i, 0, n)
#define REPS(i, a, b) reps(i, a, b)
#define REP(i, n) rep(i, n)
#define deps(i, a, b) for (int i = a; i >= b; --i)
#define dep(i, n) deps(i, n, 0)
#define DEPS(i, a, b) deps(i, a, b)
#define DEP(i, n) dep(i, n)

#define pf push_front
#define pb push_back
#define mp make_pair
#define fst first
#define FST fst
#define sec second
#define SEC sec
#define sz(obj) ((int)(obj).size())
#define all(v) (v).begin(), (v).end()
#define ALL(v) all(v)

const int INF = 999999999;
const int MOD = 1e9 + 7;
const int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

vector<string> split(const string &s, char delim) {
  vector<string> elems;
  string item;
  for (char ch: s) {
    if (ch == delim) {
      if (!item.empty()) elems.push_back(item);
      item.clear();
    }
    else item += ch;
  }
  if (!item.empty()) elems.push_back(item);
  return elems;
}

inline bool inside(int y, int x, int H, int W) {return y >= 0 && x >= 0 && y < H && x < W;}
inline int in() {int x; std::cin >> x; return x;}
template <typename T>
void print(std::vector<T>& v, char c = ' ') {
  REP(i, v.size()) {
    if (i != 0) std::cout << c;
    std::cout << v[i];
  }
  std::cout << endl;
}
template <typename T> void print(T x) { std::cout << x << '\n'; }

/****************************************************************/
//}}}

vector<set<int>> s(2);
int n;

void game(int a, int player){
  if (!sz(s[0]) or !sz(s[1])) return;
  auto itr = s[player].upper_bound(a);
  if (itr == s[player].end()) {
    game(0, abs(player - 1));
    return;
  }
  s[player].erase(*itr);
  game(*itr, abs(player - 1));
}

signed main()
{
  while (cin >> n, n) {
    rep(i, 2) s[i].clear();
    rep(i, n) s[0].insert(in());
    reps(i, 1, n * 2 + 1) if (s[0].find(i) == s[0].end()) s[1].insert(i);
    game(0, 0);

    reverse(all(s));
    for (auto a : s) print(sz(a));
  }

  return (0);
}

Measured memory_bytes: 3140
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] array = new int[n];
        int[] answer = new int[n];
        int sum = 0;
        
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            array[i] = num;
            sum += num;
        }
        
        int sum2 = sum;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 1) {
                sum2 -= array[i] * 2;
            }
        }
        answer[0] = sum2;
        
        for (int i = 1; i < n; i++) {
            answer[i] = array[i - 1] * 2 - answer[i - 1];
        }
        
        for (int i = 0; i < n; i++) {
            System.out.println(answer[i]);
        }
    }
}


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

string a, b;

int main() {
  cin >> a >> b;
  if (a.size() < b.size()) {
    cout << "LESS" << endl;
  } else if (a.size() > b.size()) {
    cout << "GREATER" << endl;
  } else {
    int cnt;
    for (cnt = 0; cnt < a.size(); cnt++) {
      if (a[cnt] == b[cnt]) continue;
      if (a[cnt] < b[cnt]) {
        cout << "LESS" << endl;
      } else {
        cout << "GREATER" << endl;
      }
      break;
    }
    if (cnt == a.size()) cout << "EQUAL" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.buffer.readline
n,k = map(int,input().split())
x = [int(i) for i in input().split()]
l = []
r = []
for i in x:
  if i < 0:
    l.append(-i)
  else:
    r.append(i)
    
l = l[::-1]

if l == []:
  print(r[k-1])
elif r == []:
  print(l[k-1])
elif k == 1:
  print(min(r[0],l[0]))
else:
  L = len(l)
  R = len(r)
  ans = 3*10**8
  if L > k-1:
    ans = l[k-1]
  if R > k-1:
    ans = min(ans,r[k-1])
  for i in range(max(L,R)):
    if i < R and 0 <= k-2-i <= L-1 :
      ans = min(ans,r[i]*2+l[k-2-i])
    if i < L and 0 <= k-2-i <= R-1:
      ans = min(ans,l[i]*2+r[k-2-i])
  print(ans)

Measured memory_bytes: 12496
S = input()
N = S.count('W')

B = [b for b in range(1, N + 1) if S[b-1] == 'B']
W = [w for w in range(N+1, len(S)+1) if S[w-1] == 'W']
# assert len(B) == len(W)

print(sum(W) - sum(B))

Measured memory_bytes: 11400
import numpy as np

H, W = map(int, input().split())
N = int(input())
A = map(int, input().split())

canvas = np.zeros((H * W, ), dtype=np.object)
idx = 0

for color, a in enumerate(A):
    for _ in range(a):
        canvas[idx] = str(color + 1)
        idx += 1

for r, row in enumerate(canvas.reshape((H, W))):
    print(" ".join(row if not r % 2 else row[::-1]))

Measured memory_bytes: 14536
from collections import defaultdict as dd
N, K, Q = map(int, input().split())
A = []
B = dd(int)
for _ in range(Q):
    a = int(input())
    a -= 1
    A.append(a)
    B[a] += 1

# K回以上他の人が答えたら敗退
# 自分はQ-K回より多く回答していたら勝ち抜け
for i in range(N):
    if B[i] >  Q- K:
        print('Yes')
    else:
        print('No')


Measured memory_bytes: 68056
#include <iostream>

bool divisibleByThree(int i) {
	return i % 3 == 0;
}

bool hasThree(int i) {
	int x = i;
	while (x) {
		if (x % 10 == 3)
			break;
		x /= 10;
	}
	return x;
}

int main()
{
	int n;
	std::cin >> n;

	for (int i = 1; i <= n; i++) {
		if (divisibleByThree(i) || hasThree(i))
			std::cout << " " << i;
	}
	std::cout << "\n";

    return 0;
}




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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define ALL(name) name.begin(),name.end()
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010

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

    int N;
    cin >> N;
    vector<double> V;
    REP(i, N) {
        double v;
        cin >> v;
        V.push_back(v);
    }
    SORT(V);

    double ans = V[0];
    for(int i = 1; i < N; ++i) {
        ans += V[i];
        ans /= 2.0;
    }

    printf("%.6f\n", ans);

    return 0;
}


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

using namespace std;

int main() {
    string s;
    cin >> s;
    long long res = 0;
    int cnt = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'B') cnt++;
        else res += cnt;
    }
    cout << res << endl;
    return 0;
}


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

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

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

int N, K;
vector<Pii> kibou;
vector<Vl> imos;

void imos2d(int a1, int b1, int a2, int b2) {
    ++imos[a1][b1];
    --imos[a1][b2];
    --imos[a2][b1];
    ++imos[a2][b2];
}

void writeimos(int lx, int ux, int ly, int uy) {
    if (lx > ux && ly > uy) {
        imos2d(lx, ly, 2 * K, 2 * K);
        imos2d(0, 0, ux, uy);
        imos2d(0, ly, ux, 2 * K);
        imos2d(lx, 0, 2 * K, uy);
    }
    else if (lx > ux) {
        imos2d(lx, ly, 2 * K, uy);
        imos2d(0, ly, ux, uy);
    }
    else if (ly > uy) {
        imos2d(lx, ly, ux, 2 * K);
        imos2d(lx, 0, ux, uy);
    }
    else {
        imos2d(lx, ly, ux, uy);
    }
}

int main() {
#ifdef FASTIO
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef FILEINPUT
    ifstream ifs("./in_out/input.txt");
    cin.rdbuf(ifs.rdbuf());
#endif

    cin >> N >> K;
    kibou.resize(N);
    for (ll i = 0; i < N; i++) {
        int x, y;
        char c;
        cin >> x >> y >> c;
        if (c == 'B') {
            x += K;
        }
        x %= 2 * K;
        y %= 2 * K;
        kibou[i] = make_pair(x, y);
    }

    imos.assign(2 * K + 1, Vl(2 * K + 1));

    for (ll i = 0; i < N; i++) {
        int x, y;
        tie(x, y) = kibou[i];

        ll lx, ux, ly, uy;
        lx = (-x + 2 * K) % (2 * K);
        ux = (K - x + 2 * K) % (2 * K);
        ly = (-y + 2 * K) % (2 * K);
        uy = (K - y + 2 * K) % (2 * K);

        writeimos(lx, ux, ly, uy);

        lx = (K - x + 2 * K) % (2 * K);
        ux = (-x + 2 * K) % (2 * K);
        ly = (K - y + 2 * K) % (2 * K);
        uy = (-y + 2 * K) % (2 * K);

        writeimos(lx, ux, ly, uy);
    }

    for (ll i = 0; i < 2 * K; i++) {
        for (ll j = 0; j <= 2 * K; j++) {
            imos[i + 1][j] += imos[i][j];
        }
    }
    for (ll i = 0; i <= 2 * K; i++) {
        for (ll j = 0; j < 2 * K; j++) {
            imos[i][j + 1] += imos[i][j];
        }
    }

    ll ans = 0;
    for (ll i = 0; i < 2 * K; i++) {
        for (ll j = 0; j < 2 * K; j++) {
            ans = max(ans, imos[i][j]);
        }
    }

    cout << ans << "\n";

    return 0;
}

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

using namespace std;

typedef long long ll;

ll MOD = 1000000007;

ll inverse(ll a)
{
	ll pow = MOD - 2;
	ll res = 1;
	while (pow)
	{
		if (pow & 1) res = res * a % MOD;
		a = a * a % MOD;
		pow /= 2;
	}
	return res;
}

int n;
string s;
int cache[11123][5123];
bool seen[11123][5123];

int dp(int t, int k)
{
	if (t == 0 && k == 0) return 1;
	if (k == 0 && t) return 0;
	if (seen[t][k]) return cache[t][k];
	seen[t][k] = true;

	// now k > 0, t whatever

	ll ans = 0;
	if (t)
		ans = (ans + 2*dp(t-1, k-1)) % MOD;
	ans = (ans + dp(t+1, k-1)) % MOD;
	if (!t)
		ans = (ans + dp(t, k-1)) % MOD;
	cache[t][k] = ans;
	return ans;
}

int main()
{
	cin >> n >> s;
	ll ans = dp(s.length(), n);
	//cout << ans << '\n';
	const ll inv = inverse(2);
	for (int i = 0; i < s.length(); i++)
		ans = (ans * inv) % MOD;
	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 183936
#include <string>
#include <math.h>
#include <iostream>
 
using namespace std;
 
int main()
{
  int a, b, c;
  cin >> a >> b >> c;
  if (a == b && b == c)
    cout << "1";
  else if (a == b)
    cout << "2";
  else if (a == c)
    cout << "2";
  else if (c == b)
    cout << "2";
  else
    cout << "3";
}

Measured memory_bytes: 3532
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
using namespace std;

// #define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
ll mod = (1000000007LL);
inline ll Mod(ll a, ll b){return (a%b);}
inline ll poww(ll a, ll b){ll res = 1;while (b > 0){if(b & 1) res = (res * a)%mod;a = (a * a)%mod;b >>= 1;}return res;}
ll gcd (ll a, ll b) { while (b) { a %= b,swap(a, b);}return a;}
void read(vector<int> &w, int n){w.resize(n);for(int i = 0; i < n; i++) cin>>w[i];}
void print(vector<int> &w){for(int i =0; i < sz(w); i++){if(i == sz(w) - 1) cout<<w[i]<<"\n";else cout<<w[i]<<" ";}}
int prodmod(vector<int> w);
int summod(vector<int> w);
///CUIDADO COM MAXN
#define N 300050

int n, m, q, k, v[N], ans;
pii w[N];
string s;

int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0);
	int n = 5;
	for(int i = 1; i<=n;i++){
		int x;
		cin>>x;
		if(x == 0){
			cout<<i<<"\n";
			return 0;
		}
	}
}
/*
    CUIDADO COM MAXN, MOD, OVERFLOW 
    >Colocar (>DEFINE INT LONG LONG<) no inicio do template
    >mod = (1e9 + 7), por padrao (NAO ESQUECER DE ALTERAR)
    >NAO ESQUECER DEFINE INT LONG LONG
    > N = 1 ? 
*/
int summod(vector<int> w){int curr=0;for(int i=0;i<sz(w); i++){curr = (curr+w[i])%mod;if(curr<0)curr+=mod;}return curr;}
int prodmod(vector<int> w){int curr = 1;
for(int i = 0; i < sz(w); i++){if(w[i] >= mod) w[i] %= mod;curr = (curr * w[i]) % mod;if(curr < 0) curr += mod;}return curr;}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;

const int INF = 1e9;
const int SIZE = 20;
string s[SIZE];
int d[SIZE][SIZE];
int h, w, sy, sx, gy, gx;
int dy[4] = {1, 0, -1, 0};
int dx[4] = {0, 1, 0, -1};
bool contain(int y, int x){
	return (0 <= y && y < h && 0 <= x && x < w);
}

int bfs(){
	rep(i, 0, h) rep(j, 0, w) d[i][j] = INF;
	queue<P> q;
	q.push(P(sy,sx));
	d[sy][sx] = 0;
	while(!q.empty()){
		P p = q.front(); q.pop();
		if(p.first == gy && p.second == gx){
			return d[gy][gx];
		} 
		for(int i = 0; i < 4; i++){
			int ny = p.first + dy[i];
			int nx = p.second + dx[i];
			if(!contain(ny, nx)) continue;
			if(s[ny][nx] =='#' || d[ny][nx] != INF) continue;
			d[ny][nx] = d[p.first][p.second] + 1;
			q.push(P(ny,nx));
		}
	}
	return INF;
}

signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cin >> h >> w;
	rep(i, 0, h) cin >> s[i];
	int ans = 0;
	rep(i, 0, h){
		rep(j, 0, w){
			if(s[i][j] == '#') continue;
			rep(p, 0, h){
				rep(q, 0, w){
					if(s[p][q] == '#') continue;
					sy = i; sx = j;
					gy = p; gx = q;
					ans = max(ans, bfs());
				}
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)

n = int(input())
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    g[a].append([b,i])
ans = [None] * (n-1)

def dfs(now, color):
    cnt = 1
    for to, num in g[now]:
        if cnt == color:
            cnt += 1
        ans[num] = cnt
        dfs(to, cnt)
        cnt += 1
dfs(0, 0)
print(max(ans))
print(*ans, sep='\n')

Measured memory_bytes: 71032
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if(a+b == c+d){
        cout << "Balanced" << endl;
    }
    else if (a+b > c+d){
        cout << "Left" << endl;
    }
    else { 
        cout << "Right" << endl;
    }
}

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

int main(){
 int n,b,f,r,v;
 cin >> n;
 int tmp[4][3][10]={};

 for(int i=0;i<n;i++){
 cin >> b >> f >> r >> v;
 tmp[b-1][f-1][r-1] += v;
 }
 for(int i=0;i<4;i++){
  for(int j=0;j<3;j++){
   for(int k=0;k<10;k++){
    cout <<" "<< tmp[i][j][k] ;
   }
   cout<<endl;
  }
 if(i!=3) cout << "####################" << endl;
 }

}


Measured memory_bytes: 3112
#include <bits/stdc++.h>
#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 namespace std;
using P = pair<int, int>; 
using ll = long long;

int main()
{
  int n, l;
  cin >> n >> l;
  string s[n];
  rep(i, n) cin >> s[i];
  sort(s, s + n);
  rep(i, n) cout << s[i];
  return 0;
}

Measured memory_bytes: 3612
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<cmath>
#include<set>
#include<random>
#include<map>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const long long mod = 1000000007;
const long long inf = 11451419198109130;
typedef pair<int, int> P;
typedef pair<int,P> PP;
struct edge { int to, cor; };
int w[105], v[105];
int dp[101][100005];
signed main() {
	int n, W; cin >> n >> W;
	rep(i, n)cin >> w[i] >> v[i];
	rep(i, n) {
		rep(j, W + 1) {
			dp[i + 1][j] = max(dp[i][j], dp[i + 1][j]);
			if (j + w[i] <= W)dp[i + 1][j + w[i]] = max(dp[i + 1][j + w[i]], dp[i][j] + v[i]);
		}
	}
	rep(i, W)dp[n][i + 1] = max(dp[n][i + 1], dp[n][i]);
	cout << dp[n][W] << endl;
}

Measured memory_bytes: 78336
A, B, C, D = map(int, input().split())
M = [[A, B], [C, D]]
T, A = 0, 1
HP, AP = 0, 1
i = 0
while M[T][HP] * M[A][HP] > 0:
    if i % 2 == T:   # turn T
        M[A][HP] -= M[T][AP]
    else:   # turn A
        M[T][HP] -= M[A][AP]
    i += 1
if M[T][HP] > 0:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 8948
#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;


// Union-Findの実装
const int MAX_N = 10000; // 今回の場合、頂点の数の最大値

struct UnionFind
{
  // par[i]:要素iが属する木の親の番号、i==par[i]のときは要素iが木の根となる
  int par[MAX_N];
  
  // rank[i]:根が要素iの木の高さ(ランク)
  int rank[MAX_N];
  
  // コンストラクタ
  // 各要素iが要素iを根とする高さ0の木に存在するものとして初期化を行う
  UnionFind(int n){
    for(int i = 0; i < n; i++){
      par[i] = i;
      rank[i] = 0;
    }
  }

  // 要素xが属する木の根を得るメソッド
  int find(int x){
    if(par[x] == x) return x;
    else return par[x] = find(par[x]);
  }

  // 2つの要素xとyが属する木を併合するメソッド
  void unite(int x, int y){
    x = find(x);
    y = find(y);

    // 既に同じ木に属している場合
    if(x == y) return;

    // 効率化の工夫としてランクが低いものから高いものへ辺を張る
    if(rank[x] < rank[y]) par[x] = y;
    else{
      par[y] = x;
      if(rank[x] == rank[y]) rank[x]++; // ランクが等しい場合
    }
  }

  // 2つの要素xとyが属する木の根が同じならtrueを返すメソッド
  bool same(int x, int y){
    return find(x) == find(y);
  }
};

// 辺の情報を表す構造体
struct Edge{
  int u, w;
  double cost;
};

// Edgeをコストの小さい順にソートするための比較関数
bool comp(const Edge &e1, const Edge &e2)
{
  return e1.cost < e2.cost;
}

const int MAX_E = 100000; // 辺の数の最大値
Edge es[MAX_E]; // グラフ上の辺を保存する配列
int v, e; // 頂点の数と辺の数


double kruskal()
{
  sort(es, es + e, comp); // 辺をコストの小さい順にソート
  UnionFind uf(v); // Union-Findの準備
  double ans = 0; // 最小全域木(森)の辺の総コスト

  // 全域木に辺を追加していく
  for(int i = 0; i < e; i++){
    // コストの小さい辺から調べる
    Edge et = es[i];

    // もし辺の両端の頂点が同じ連結成分属していないならば
    if(!uf.same(et.u, et.w)){
      uf.unite(et.u, et.w); // 同じ連結成分に属させる
      ans += et.cost; // その辺を全域木に追加
    }
  }

  return ans;
}

typedef struct sphere{
  double x, y, z, r;
} Sphere;


int main()
{
  while(1){
    int n;
    cin >> n;
    if(n == 0) break;
    v = n;
    e = 0;
    for(int i = n - 1; i > 0; i--)
      e += i;
    Sphere s[100];
    for(int i = 0; i < n; i++)
      cin >> s[i].x >> s[i].y >> s[i].z >> s[i].r;
    for(int i = 0, k = 0; i < n; i++){
      for(int j = i + 1; j < n; j++, k++){
        Edge et;
        et.u = i;
        et.w = j;
        et.cost = sqrt(pow(s[i].x - s[j].x, 2) + pow(s[i].y - s[j].y, 2) + pow(s[i].z - s[j].z, 2)) - s[i].r - s[j].r;
        if(et.cost < 0)
          et.cost = 0;
        es[k] = et;
      }
    }
    printf("%.3lf\n", kruskal());
  }
}

Measured memory_bytes: 1344
#include <stdio.h>
#include <cstdio>
#include <iostream>
#include <queue>
#include <set>

using namespace std;

int main(){
  
  int K, X;
  scanf("%d%d", &K, &X);
  
  for(int i = X-K+1; i <= X+K-1; i++){
    std::cout << i << " ";
  }
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair <int, int>;
const double PI = acos(-1);
const ll MOD = 1000000007;

int main() {
  int A, B, C, K;
  cin >> A >> B >> C >> K;

  bool h = 0;

  rep(i, K+1){
    if( A < B && B < C){
      h = 1;
      break;
    }
    if(A >= B){
      B = B * 2;
      continue;
    }
    else if(B >= C){
      C = C * 2;
      continue;
    }
  }


  if(h) cout << "Yes" << endl;
  else cout << "No" << endl;

}


Measured memory_bytes: 3592
#include<iostream>
using namespace std;
bool b;
int n,A;
string s,t;
int main()
{
	cin>>n>>s>>t;
	for(int i=1;i<=n;i++)
	{
		b=true;
		for(int j=0;j<i;j++)
			if(t[j]!=s[n-i+j])
				b=false;
		if(b)
			A=i;
	}
	cout<<2*n-A;
	return 0;
}

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

A = X
ans = A

visited = [0]*M
tmp = []

i = 2
while i <= N:
    A = (A*A) % M
    if visited[A] == 0:
        visited[A] = i
        tmp.append(A)
        ans += A
    else:
        ans += A
        loop_length = i-visited[A]
        loop_val = tmp[-1*loop_length:]
        loop_count = (N-i) // loop_length
        ans += sum(loop_val) * loop_count
        visited = [0]*M
        i += loop_length * loop_count

    i += 1

print(ans)


Measured memory_bytes: 15508
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, a, b = list(map(int, readline().split()))
    if (b - a) % 2 == 0:
        print((b - a) // 2)
    else:
        if abs(a - 1) < abs(n - b):
            c = a - 1
            b -= c
            a -= c
            if (b - a) % 2 == 0:
                print((b - a) // 2 + c)
            else:
                print(abs((b - 1) - a) // 2 + c + 1)
        elif abs(a - 1) >= abs(n - b):
            c = n - b
            a -= c
            b -= c
            if (b - a) % 2 == 0:
                print((b - a) // 2 + c)
            else:
                print(abs(b - (a + 1)) // 2 + c + 1)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 38384
#include <bits/stdc++.h>
#define rep(i, n) for(ll i=0;i<n;i++)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (b>a) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const long long INF = 2LL << 60;
using ll = long long;
using P = pair<ll, ll>;
struct Node{
    int num;
    int pre;
    int cnt;
};
int main(int argc, char const *argv[]){
    int n, k;
    ll ans=0;
    cin >> n >> k;
    vector<int> p(n);
    rep(i,n){
        cin >> p[i];
    }
    sort(p.begin(),p.end());
    rep(i,k){
        ans+=p[i];
    }
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 3640
N, M = map(int, input().split(' '))
ferrys = [list(map(int, input().split(' '))) for _ in range(M)]
cand1to = []
candtoN = []
for f in ferrys:
    if f[0] == 1:
        cand1to.append(f[1])
    elif f[1] == 1:
        cand1to.append(f[0])
    elif f[0] == N:
        candtoN.append(f[1])
    elif f[1] == N:
        candtoN.append(f[0])

if set(cand1to) & set(candtoN) == set([]):
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')


Measured memory_bytes: 61052
#include<iostream>
#include<string>
#include <vector>
#include<algorithm>
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using pii = pair<int, int>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define vsort(v) sort(v.begin(), v.end())
#define ll long long
const ll MOD = 1e9 + 7;

int main() {
	int n;
	cin >> n;
	vi a(n);
	rep(i, n) cin >> a[i];
	int c = 0;
	bool flag = true;
	while (flag) {
		rep(i, n) {
			if (a[i] % 2 == 0 ) a[i] /= 2;
			else {
				flag = false;
				break;
			}
		}
		if (flag) c++;
	}
	cout << c << endl;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
	int n, input, db4, db2, ndb2;
	cin >> n;
	int i;
	i = n;
	db4 = db2 = ndb2 = 0;
	while(i--) {
		cin >> input;
		if(input%4 == 0) db4++;
		else if(input&1) ndb2++;
		else db2++;
	}
	if(ndb2 == n) cout << "No";
	else if(db2+db4 == n) cout << "Yes";
	else if(db2+ndb2<=db4+1) cout << "Yes";
	else if(db4>=ndb2) cout << "Yes";
	else cout << "No";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
const Int MOD = 1000000007;
int main() {
    int N; cin >> N;
    vector<int> A(N); for (auto &a : A) cin >> a;
    Int ans = 1;
    vector<int> B = {0, 0, 0};
    for (int i = 0; i < N; i++) {
        int cnt = 0;
        for (int j = 0; j < 3; j++) {
            if (B[j] == A[i]) cnt++;
        }
        ans = (ans * cnt) % MOD;
        for (int j = 0; j < 3; j++) {
            if (B[j] == A[i]) { B[j]++; break; }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 768
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
typedef pair<int,int> P;
const int inf=1000000000000000007;
const int MOD=1000000007;
signed main(){
  int n;cin>>n;
  vector<int> a(3*n);
  rep(i,3*n)cin>>a[i];
  vector<int> f(n);
  vector<int> r(2*n);
  vector<P> nxt(2*n);
  rep(i,n)f[i]=a[i];
  rep(i,2*n){
    r[i]=a[i+n];
    nxt[i]=make_pair(a[i+n],i+n);
  }
  sort(nxt.begin(),nxt.end());
  sort(r.begin(),r.end());
  nxt.push_back(make_pair(inf,inf));
  int res=0;
  priority_queue<int,vector<int>,greater<int>> front;
  rep(i,n){
    res+=f[i]-r[i];
    front.push(f[i]);
  }
  int mini=front.top();front.pop();
  int nxt_cur=n;
  int buf=res;
  for(int i=n;i<2*n;i++){
    if(a[i]>mini){
      buf-=mini;
      buf+=a[i];
      front.push(a[i]);
      mini=front.top();
      front.pop();
    }
    if(a[i]<nxt[nxt_cur].first){
      while(i>=nxt[nxt_cur].second){
        nxt_cur++;
      }
      if(nxt_cur==2*n)break;
      buf+=a[i];
      buf-=nxt[nxt_cur].first;
      nxt_cur++;
    }
    else if(a[i]==nxt[nxt_cur].first){
      while(i>nxt[nxt_cur].second){
        nxt_cur++;
      }
      if(nxt_cur==2*n)break;
      buf+=a[i];
      buf-=nxt[nxt_cur].first;
      nxt_cur++;
    }
    res=max(res,buf);
    //cout<<buf<<"\n";
  }
  cout<<res<<"\n";
  return 0;
}


Measured memory_bytes: 13056
#! /usr/bin/env python3
# -*- coding:utf-8 -*-

def name_count(N):
    x = N%10
    if x in [2, 4, 5, 7, 9]: return "hon"
    elif x in [0, 1,6, 8]: return "pon"
    else: return "bon"

def main():
    N = int(input())
    print(name_count(N))

if __name__ == "__main__":
    main()


Measured memory_bytes: 9168
n , y = map(int , input().split())

c = 0

for o in range(n+1):
    for f in range(n+1-o):
        if 10000*n - 9000*o -5000*f == y:
            print(n-o-f , f , o)
            c = 1
            break
    if c == 1:
        break
            
if c != 1:
    print(-1 , -1 , -1)

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

#define all(x) begin(x), end(x)

using i64 = int_fast64_t;
using u64 = uint_fast64_t;
using f64 = double;
using p64 = pair<i64, i64>;

constexpr i64 INF = INT_FAST64_MAX / 2;

void solve() {
    string s;
    cin >> s;
    i64 w;
    cin >> w;

    i64 n = s.size();
    for (i64 i = 0; i * w < n; i++) cout << s[i * w];
    cout << endl;
}

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


Measured memory_bytes: 3640
n = int(input())
s = list(map(int, input().split()))
ave = sum(s) / 2
tmp = 0
i = 0
while tmp < ave:
  tmp += s[i]
  i += 1
res = sum(s) - tmp
tmp2 = tmp - s[i-1]
res2 = sum(s) - tmp2
print(min(abs(tmp2-res2), abs(tmp-res)))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int a,b,s;
int main(){
	cin>>a;
	b=a;
	while(b){
		s+=b%10;
		b/=10;
	}
	if(a%s==0) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

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

Sum_a = 0
Sum_b = 0
Min = 1000000

for i in range(N):
  Sum_a += L+i

for i in range(N):
  Sum_b = Sum_a - (L+i)
  if abs(Sum_a - Sum_b) < Min:
    Min = abs(Sum_a - Sum_b)
    Min_b = Sum_b
    
print(Min_b)

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX (int)1e5
#define FAIL { cout << "No\n"; return 0; }
int a[MAX], N;

int solve(int k) {
    int comp = 0, rem = 0, i;
    for (i = 0; i < N; i++) {
        if (a[i] < k) comp++;
        else rem++;
    }
    k -= comp;
    if (rem/2 < k || rem == 1) return 0;
    return (k >= 0 && !(k == 0 && rem > 0));

}

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

    int diff = a[N-1]-a[0];
    if (diff > 1) FAIL;
        
    int res;
    if (diff == 1) res = solve(a[N-1]);
    else res = max(solve(a[N-1]), solve(a[N-1]+1));
    cout << (res ? "Yes\n" : "No\n");
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int val[131088], p;
int sum(int r) {
	int ret = 0;
	while(r > 0) {
		ret += val[r];
		r -= r & -r;
	}
	return ret;
}
void add(int i, int x) {
	while(i <= 1 << p) {
		val[i] += x;
		i += i & -i;
	}
}
int n, q, tp, x, y;
int main() {
	scanf("%d%d", &n, &q);
	p = 32 - __builtin_clz(n);
	while(q--) {
		scanf("%d%d%d", &tp, &x, &y);
		if(tp == 0) add(x, y);
		else {
			int ret = sum(y) - sum(x - 1);
			printf("%d\n", ret);
		}
	}
	return 0;
}

Measured memory_bytes: 3544
import math

def solve():
    ans = [-1 for i in range(n+1)]
    remaining = set(range(1, n+1))
    remaining.remove(1)
    last_visited = [1]
    last_visited2 = []
    while remaining:
        c = len(remaining)
        for r in last_visited:
            for ad in adj[r]:
                if ad in remaining:
                    last_visited2.append(ad)
                    remaining.remove(ad)
                    ans[ad] = r
        last_visited = last_visited2
        last_visited2 = []
        if len(remaining) == c:
            print("No")
            return
    print("Yes")
    for i in ans[2:]:
        print(i)
    return

n, m = [int(ii) for ii in input().split()]
adj = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = [int(ii) for ii in input().split()]
    adj[a].append(b)
    adj[b].append(a)
solve()

Measured memory_bytes: 114464
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<int> L(N);
    rep(i, N) cin >> L[i];
    sort(L.begin(), L.end());
    L.push_back(INF);
    int ans = 0;
    rep(i, N - 2) {
        REP(j, i + 1, N - 2) {
            int upper = L[i] + L[j];
            int lower = L[j] - L[i];
            auto itr1 = upper_bound(L.begin()+j+1, L.end(), lower);
            auto itr2 = lower_bound(L.begin()+j+1, L.end(), upper);
            itr2--;
            //cout << ab <<  " " << (L.end() - itr) << " " << *itr << endl;
            //cout << max(0,itr2 - itr1 + 1) << endl;
            //if (*itr2 == INF) continue;
            ans += max((int)0,(int)(itr2 - itr1 + 1));
            //cout << *itr2 << " " << *itr1 << endl;
            //dump(L.end() - itr);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())

MOD = 10**9 + 7
MAX = m + 1
fact = [1] * (MAX + 1)  # i!
finv = [1] * (MAX + 1)  # (i!)^{-1}
iinv = [1] * (MAX + 1)  # i^{-1}
for i in range(2, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * iinv[i] % MOD


def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    return (fact[n] * finv[k] % MOD) * finv[n - k] % MOD


def perm(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    return fact[n] * finv[n - k] % MOD


ans = perm(m, n)
for i in range(1, n + 1):
    ans += (-1)**(i % 2) * comb(n, i) * perm(m - i, n - i) % MOD
    ans %= MOD

ans *= perm(m, n)
ans %= MOD

print(ans)


Measured memory_bytes: 87156
#include <iostream>
#include <vector>
#include <deque>
#include <map>
#include <algorithm>
#include <string>
#include <cmath>

#define ull unsigned long long
#define ll long long
#define ul unsigned long

using namespace std;

int main()
{
	ul A = 0;
	ul B = 0;
	ul N = 0;
	cin >> N >> A >> B;

	ul japan_counter = 0;
	ul other_counter = 0;
	for(ul i = 0; i < N; ++i)
	{
		unsigned char value = 0;
		cin >> value;
		if(value == 'a')
		{
			if(japan_counter + other_counter < A + B)
			{
				japan_counter++;
				cout << "Yes" << endl;
			}
			else
			{
				cout << "No" << endl;
			}
			continue;
		}
		if(value == 'b')
		{
			if(japan_counter + other_counter < A + B && other_counter < B)
			{
				other_counter++;
				cout << "Yes" << endl;
			}
			else
			{
				cout << "No" << endl;
			}
			continue;
		}
		cout << "No" << endl;
	}
	return 0;
}

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

int main() {
    int a, b;
    cin >> a >> b;
    int ans = 0;
    if (a <= 5) ans = 0;
    else if (6 <= a && a <= 12) ans = b/2;
    else ans = b;
    cout << ans << endl;
    return 0;
}


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


int main(){
  string S;
  cin >> S;
  set<char> T;
  for(auto& s : S){
    T.insert(s);
  }
  cout << (S.size() == T.size() ? "yes" : "no") << endl;
  return 0;
}

Measured memory_bytes: 256
n = gets.chomp.to_i
s = gets.chomp
sum = Array.new(n, 0)
sum[0] = s[1..-1].count('E')
1.upto(n-1) do |i|
  if s[i-1] == 'W'
    sum[i] = sum[i-1] + 1
  else
    sum[i] = sum[i-1]
  end
  if s[i] == 'E'
    sum[i] -= 1
  end
end
puts sum.min


Measured memory_bytes: 4868
/* Stack */

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

/* Inplement stack by array */
int S[3];
int top = 0;

void push(int v)
{
    top++;
    S[top] = v;
}

int pop(void)
{
    top--;
    return S[top + 1];
}

int main(void)
{
    char s[100];

    while (scanf("%s", s) != EOF) {
        int a, b;
        if (s[0] == '+') {
            a = pop();
            b = pop();
            push(a + b);
        }
        else if (s[0] == '-') {
            a = pop();
            b = pop();
            push(b - a);
        }
        else if (s[0] == '*') {
            a = pop();
            b = pop();
            push(a * b);
        }
        else
            push(atoi(s));
    }

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

    return 0;
}

Measured memory_bytes: 548
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

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

        int N = scanner.nextInt();

        List<Integer> list = new ArrayList();
        for (int i = 0; i < N; i++) {
            list.add(scanner.nextInt());
        }

        int result = 0;

        boolean shouldContinue = true;
        while(shouldContinue) {
            for (int value : list) {
                if (value % 2 != 0) {
                    shouldContinue = false;
                    break;
                }
            }
            if (shouldContinue) {
                List<Integer> newList = new ArrayList();
                boolean hasPositive = false;
                for (int value : list) {
                    if (value / 2 > 0) {
                        hasPositive = true;
                    }
                    newList.add(value / 2);
                }
                list = newList;
                result++;
                if (!hasPositive) {
                    shouldContinue = false;
                }
            }
        }

        System.out.println(result);
    }
}

Measured memory_bytes: 23892
N = int(input())
H = list(map(int,input().split()))
ans = 'Yes'
for i in range(N-1):
    if H[i+1] -H[i] >= 1:
        H[i+1] -= 1
    if H[i]-H[i+1] >= 1:
        ans = 'No'
        break
print(ans)

Measured memory_bytes: 14224
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<int>; using VVI = vector<VI>; using VVVI = vector<VVI>;
const int inf=1e9+7;
const ll INF=1LL<<60;

const ll Mod=1000003;

vector<ll> inv,fact,invfact;
void Mod_build(int n=2010101){
	fact.resize(n+1);
	inv.resize(n+1);
	invfact.resize(n+1);
	fact[0]=inv[0]=invfact[0]=1;
	inv[1]=1;
	for(ll i=0;i<n;i++){
		fact[i+1]=fact[i]*(i+1)%Mod;
		if(i>0)inv[i+1]=Mod-inv[Mod%(i+1)]*(Mod/(i+1))%Mod;
		invfact[i+1]=invfact[i]*inv[i+1]%Mod;
	}
}
ll perm(int n,int k){
	if(n<0||k<0||k>n)return 0;
	return fact[n]*invfact[n-k]%Mod;
}
ll comb(int n,int k){
	if(n<0||k<0||k>n)return 0;
	return (fact[n]*invfact[n-k]%Mod)*invfact[k]%Mod;
}
ll powMod(ll n,ll k){
	k%=Mod-1;
	if(k<0)k+=Mod-1;
	ll ret=1;
	while(k){
		if(k&1)ret=ret*n%Mod;
		n=n*n%Mod;
		k>>=1;
	}
	return ret;
}


int main(){
  int i,j;
  int q;
  cin>>q;
  Mod_build();
  for(i=0;i<q;i++){
    int x,d,n;
    cin>>x>>d>>n;
    int y=x*inv[d]%Mod;
    if(d%Mod==0){
      cout<<powMod(x,n)<<endl;
    }
    else if(y+n+1>=2010101) {
      cout<<0<<endl;
    }
    else{
      int ans=fact[y+n-1]*invfact[max(y-1,0)]%Mod;
      ans=ans*powMod(d,n)%Mod;
      cout<<ans<<endl;
    }
  }
}

Measured memory_bytes: 48000
a = input()

q = int(input())

queries = [list(input().split()) for i in range(q)]

revers = False

head = []

tail = []

for query in queries:
    if len(query) == 1:
        revers = not revers
    else:
        command, f, chara = query
        if f == '1':
            if not revers:
                head.append(chara)
            else:
                tail.append(chara)
        else:
            if not revers:
                tail.append(chara)
            else:
                head.append(chara)

# print(revers)
#
# print(head)
#
# print(tail)

if revers:
    tail.reverse()
    print(''.join(tail) + a[::-1] + ''.join(head))
else:
    head.reverse()
    print(''.join(head) + a + ''.join(tail))

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

int main()
{
    int n; cin>>n;
    map<int,int>cnt;

    for(int i=0; i<n; i++){
        int input;cin>>input;
        cnt[input]++;
    }
    int ans=0;
    for(auto u:cnt){
        if(u.first<=u.second) ans+=(u.second-u.first);
        else {ans+=u.second;}
    }
    cout<<ans<<endl;
    return 0;

}

Measured memory_bytes: 8064
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int K = scan.nextInt();
        int[] dp = new int[K];
        Arrays.fill(dp,Integer.MAX_VALUE);

        class Node{
            int to,cost;
            Node(int to,int cost){
                this.to=to;
                this.cost=cost;
            }
        }

        PriorityQueue<Node> que = new PriorityQueue<>((a,b) -> a.cost-b.cost);
        for(int i=1;i<Math.min(10,K);++i){
            dp[i]=i;
            que.add(new Node(i,i));
        }
        while(!que.isEmpty()){
            Node node = que.poll();
            int v = node.to;
            int c = node.cost;
            if(c > dp[v])continue;
            for(int i=0;i<10;++i){
                int nextv = (v*10+i)%K;
                int nextc = c+i;
                if(dp[nextv] > nextc){
                    dp[nextv]=nextc;
                    que.add(new Node(nextv,nextc));
                }
            }
        }
        System.out.println(dp[0]);
    }
}

Measured memory_bytes: 35612
#include "bits//stdc++.h"
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = 998244353;

#define rep(i,n) for (int i = 0; i < (n); i++)
#define ALL(v) v.begin(), v.end()
typedef pair<int, int> P;
int A[100000];
int main() {
	int N, M;
	cin >> N >> M;
	rep(i, N) cin >> A[i];
	sort(A, A + N);
	ll ans = 0;
	rep(i, N) ans += A[i];
	vector<P> vec;
	rep(i, M) {
		int B, C;
		cin >> B >> C;
		vec.emplace_back(C, B);
	}
	sort(ALL(vec), greater<P>());
	int now = 0;
	for (int i = 0; i < N; i++) {
		if (vec.size() <= now) break;
		if (A[i] >= vec[now].first) break;
		ans -= A[i];
		ans += vec[now].first;
		vec[now].second--;
		if (vec[now].second == 0) now++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1784
use proconio::input;

fn main() {
    input!{
        k :u64,
        a: u64,
        b: u64,
    }
    let mut ans = "NG";
    for i in a..b + 1{
        if i % k == 0 { ans = "OK" };
    }
    println!("{}", ans);
}


Measured memory_bytes: 2176
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

int main(){
	int n;
	cin >> n;
	vector<int> a(n);
	rep(snip_i, n) cin >> a.at(snip_i);
	sort(a.begin(), a.end(), greater<int>());
	int h, w;
	h = w = -1;
	rep(i, n-1){
		if(a.at(i) != a.at(i+1))continue;
		if(h == -1){
			h = a.at(i);
			i++;
		}else{
			w = a.at(i);
			break;
		}
	}
	if(w == -1){
		cout << 0 << endl;
	}else{
		ll ans = (ll)w * (ll)h;
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 768
r, c, k = map(int, input().split())
v = [map(int, input().split()) for _ in range(k)]

sq = [[0 for _ in range(c)] for _ in range(r)]
for ri, ci, vi in v:
    sq[ri - 1][ci - 1] = vi

dp = [[[0 for _ in range(c)] for _ in range(4)] for _ in range(2)]
for ri in range(r):
    if 0 < ri:
        for ci in range(c):
            dp[ri % 2][0][ci] = max([dp[1 - ri % 2][i][ci] for i in range(4)])
            for i in range(1, 4):
                dp[ri % 2][i][ci] = 0
    for ci in range(c):
        if 0 < ci:
            for i in range(4):
                dp[ri % 2][i][ci] = max(dp[ri % 2][i][ci], dp[ri % 2][i][ci - 1])
        if 0 < sq[ri][ci]:
            for i in range(2, -1, -1):
                dp[ri % 2][i + 1][ci] = max(dp[ri % 2][i + 1][ci], dp[ri % 2][i][ci] + sq[ri][ci])

ans = max([dp[ri % 2][i][-1] for i in range(4)])
print(ans)

Measured memory_bytes: 205808
n=gets.chomp.to_i
a=2.times.map { gets.chomp.split(" ").map { |e| e.to_i } }

max = 0

for i in 0..n-1 do
  sum = a[0][0..i].inject(:+)
  sum += a[1][i..n-1].inject(:+)
  max = max > sum ? max : sum
end

puts max

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

using ll = long long;
using namespace std;
const int INFint = 1e9+1;
const ll INFll = (ll)1e18+1;
ll MOD=998244353;


int main(){
  ll N,K;
  cin>>N>>K;
  vector<ll> L(K),R(K);
  for(int i(0);i<K;i++){
    cin>>L[i]>>R[i];
  }
  ll dp[200001] = {0}, r[200001] = {0};
  dp[1] = 1;
  ll tmp(0);
  for(int i(1);i<=N;i++){
    tmp += r[i]; tmp %= MOD;
    if(tmp < 0) tmp += MOD;
    if(i != 1) dp[i] = tmp;
    for(int k(0);k<K;k++){
      if(i+L[k] <= N){
        r[i+L[k]] += dp[i];
        r[i+L[k]] %= MOD;
      }
      if(i+R[k]+1 <= N){
        r[i+R[k]+1] -= dp[i];
        //if(r[i+R[k]+1] < 0) dp[]
      }
    } 
  }
  cout << dp[N] << endl;
  return 0;
}



Measured memory_bytes: 6716
def main(n: int, s: str, k: int):
    rp = s[k - 1]

    for s in s:
        if s != rp:
            print("*", end="")
        else:
            print(rp, end="")


if __name__ == "__main__":
    n = int(input())
    s = input()
    k = int(input())

    main(n, s, k)


Measured memory_bytes: 2940
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
def end_of_loop():raise StopIteration
    
    
def main():
    X, K, D = MI()
    #計算処理簡単のため
    X = abs(X)
    if K*D <= X:
        print(X-K*D)
        sys.exit()
    syou = X // D
    amari = X % D
    if (K - syou) % 2 == 0:
        print(amari)
    else:
        print(abs(amari-D))

if __name__ == "__main__":
    main()

Measured memory_bytes: 9628
S = input()
K = int(input())
S_list = [i for i in S]
answer = []
for i in range(1, 4):
    S_rep = S_list * i
    S_ans = 0
    for j in range(len(S_rep) - 1):
        if S_rep[j] == S_rep[j + 1]:
            S_ans += 1
            S_rep[j + 1] = "A"
    answer.append(S_ans)

def_S = [answer[1] - answer[0], answer[2] - answer[1]]

if K == 1:
    print(answer[0])
elif (K - 1) % 2 == 0:
    print(answer[0] + sum(def_S) * (K - 1) // 2)
else:
    print(answer[0] + sum(def_S) * (K - 2) // 2 + def_S[0])


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

int main() {
  int a,b,c,k;
  cin >> a >> b >> c >> k;
  
  if(a>=k){
    cout << k << endl;
  }
  else if((a+b)>=k){
    cout << a << endl;
  }
  else{
    k=k-(a+b);
    int ans=a-k;
    cout << ans << endl;
  }
}


Measured memory_bytes: 3616