akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>

int main(void) {
	int a, b, c;
	while(scanf("%d %d %d\n", &a, &b, &c) == 3) {
		if(a == -1 && b == -1 && c == -1)
			break;
		
		/*
		    中間試験、期末試験のいずれかを欠席した場合成績は F。
		    中間試験と期末試験の合計点数が 80 以上ならば成績は A 。
		    中間試験と期末試験の合計点数が 65 以上 80 未満ならば成績は B。
		    中間試験と期末試験の合計点数が 50 以上 65 未満ならば成績は C。
		    中間試験と期末試験の合計点数が 30 以上 50 未満ならば成績は D。 ただし、再試験の点数が 50 以上ならば成績は C。
		    中間試験と期末試験の合計点数が 30 未満ならば成績は F。
		*/
		if(a == -1 || b == -1) {
			printf("F\n");
		} else if(a + b >= 80) {
			printf("A\n");
		} else if(a + b >= 65) {
			printf("B\n");
		} else if(a + b >= 50) {
			printf("C\n");
		} else {
			if(c >= 50) {
				printf("C\n");
			} else if(a + b >= 30) {
				printf("D\n");
			} else {
				printf("F\n");
			}
		}
	}
	return 0;
}

Measured memory_bytes: 588
#include<iostream>
using namespace std;
int main(){
int n;
while(cin>>n){
int counter=0;
for(int a=0;a<10;a++){
for(int b=0;b<10;b++){
for(int c=0;c<10;c++){
if(0<=n-a-b-c && n-a-b-c<=9){
counter++;
}
}
}
}
cout<<counter<<endl;
}
return 0;
}

Measured memory_bytes: 1160
#include<iostream>
using namespace std;
int a,b,c,d,i;
int main (){
	cin>>a>>b>>c>>d;
	while(a>0&&c>0){
		c=c-b;
		if(c<=0){
			break;
		}
		a=a-d;
	}
	if(a>c){
		cout<<"Yes";
	}
	else{
		cout<<"No";
	}
	
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long int
#define ld long double
#define pii 3.14
#define mod (ll)(1e9+7)
#define inf (ll)(1e18)
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ordered_set tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
#define pi pair<int,int>
#define N (ll)(1e5 + 5)


void solve()
{
    ll d,t,s;
    cin>>d>>t>>s;

    if(s*t >= d)
        cout<<"Yes";
    else
        cout<<"No";

}

int main()
{
    fio;
    ll tc = 1;
    //cin>>tc;
    while(tc--)
    {
        solve();
    }
}


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

#define NIL NULL

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};

typedef struct node * Node;

Node root;

Node treeMinimum(Node x){
  while(x->left != NIL){
    x = x->left;
  }
  return x;
}

Node treeSearch(Node u, int k){
  if(u == NIL || k == u->key) return u;
  if(k < u->key) return treeSearch(u->left, k);
  else return treeSearch(u->right, k);
}

Node treeSuccessor(Node x){
  Node y;
  if(x->right != NIL) return treeMinimum(x->right);
  y = x->parent;
  while(y != NIL && x == y->right){
    x = y;
    y = y->parent;
  }
  return y;
}

void treeDelete(Node z){
  Node x, y;

  if(z->left==NIL || z->right ==NIL) y=z;
  else y=treeSuccessor(z);

  if(y->left!=NIL) x=y->left;
  else x=y->right;

  if(x!=NIL) x->parent=y->parent;

  if(y->parent==NIL) root=x;
  else if(y==y->parent->left) y->parent->left=x;
  else y->parent->right=x;

  if(y!=z) z->key=y->key;
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x!=NIL){
    y = x;

    if(z->key < x->key) x = x->left;
    else x = x->right;
  }
  z->parent = y;
  if(y == NIL) root = z;
  else if (z->key < y->key) y->left = z;
  else y->right = z;

  return;
}

void inorder(Node u){
  if(u->left != NIL) inorder(u->left);
  printf(" %d", u->key);
  if(u->right != NIL)  inorder(u->right);
}

void preorder(Node u){
  printf(" %d", u->key);
  if(u->left != NIL) preorder(u->left);
  if(u->right != NIL)  preorder(u->right);
}

int main(){
  int n, i, x;
  char chil[20];

  scanf("%d", &n);

  for (i = 0; i < n; i++){
    scanf("%s", chil);
    if ( chil[0] == 'f'){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    }
    else if (chil[0] == 'i'){
      scanf("%d", &x);
      insert(x);
    }
    else if (chil[0] == 'p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
    else if (chil[0] == 'd'){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}

Measured memory_bytes: 19364
# frozen_string_literal: true

N, Q = gets.chomp.split(' ').map(&:to_i)

children = Array.new(N) { [] }
points = Array.new(N, 0)

(N - 1).times do
  a, b = gets.chomp.split(' ').map(&:to_i)
  children[a - 1] << b - 1
  children[b - 1].push(a - 1)
end

Q.times do
  q, x = gets.chomp.split(' ').map(&:to_i)
  points[q - 1] += x
end

queue = [0]
finished = Array.new(N, false)
while queue.size.positive?
  node = queue.pop
  finished[node] = true
  children[node].each do |child|
    next if finished[child]

    points[child] += points[node]
    queue.push(child)
  end
end

puts points.join(' ')


Measured memory_bytes: 26236
#include<iostream>

using namespace std;

int main() {
	int n[10000], c10[10000], c50[10000], c100[10000], c500[10000],i=0;

	while (1) {
		cin >> n[i];
		if (n[i] == 0)break;
		cin >> c10[i] >> c50[i] >> c100[i] >> c500[i];
		i++;
	}
	
	for (int j = 0; j < i; j++) {
		int m, k10, k50, k100, k500;
		m = c10[j] * 10 + c50[j] * 50 + c100[j] * 100 + c500[j] * 500 - n[j];

		k500 = c500[j] - m / 500;
		if (k500 < 0)k500 = 0;
		m -= 500 * (m / 500);

		k100 = c100[j] - m / 100;
		if (k100 < 0)k100 = 0;
		m -= 100 * (m / 100);

		k50 = c50[j] - m / 50;
		if (k50 < 0)k50 = 0;
		m -= 50 * (m / 50);

		k10 = c10[j] - m / 10;
		if (k10 < 0)k10 = 0;
		m -= 10 * (m / 10);

		if (k10 > 0)cout << 10 << " " << k10 << endl;
		if (k50 > 0)cout << 50 << " " << k50 << endl;
		if (k100 > 0)cout << 100 << " " << k100 << endl;
		if (k500 > 0)cout << 500 << " " << k500 << endl;
		if(j<i-1)cout << endl;
	}

	return 0;
}

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

int main(){
  int N,K;cin>>N>>K;
  vector<int> X(N),Y(N);
  int ans=0;
  for(int i=0;i<N;i++){
    cin>>X.at(i);
    Y.at(i)=K-X.at(i);
    ans+=min(X.at(i),Y.at(i));
  }
  cout<<ans*2<<endl;
}



Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  string S;
  bool Y = false;
  cin >> N;
  for (; N > 0; N--) {
    cin >> S; //P,W,G,Y
    if (S == "P" || S == "W" || S == "G") {
      continue;
    }
      Y = true;
  }
  if (Y) {
    cout << "Four" << endl;
  }
  else {
    cout << "Three" << endl;
  }
}


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

using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	REP(i, v.size()) { if (i)os << " "; os << v[i]; }return os;
}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
	REP(i, v.size()) { if (i)os << endl; os << v[i]; }return os;
}

const ll INF = 1LL << 60;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

#define int long long

inline void my_io() {

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	cout << fixed << setprecision(16);

	//cout << setprecision(10) << scientific << ans << endl;

}

ll n;
vector<ll> a;
vector<vector<ll>> dp(3001, vector<ll>(3001, 0));
vector<vector<ll>> used(3001, vector<ll>(3001, 0));

ll solve(ll l, ll r) {
	if (l > r) {
		return 0;
	}

	if (used[l][r]) {
		return dp[l][r];
	}

	used[l][r] = 1;

	ll res;
	ll dif = n - (r - l + 1);

	if (dif % 2 == 0) {
		res = -INF;
		res = max(res, solve(l + 1, r) + a[l]);
		res = max(res, solve(l, r - 1) + a[r]);
	}
	else {
		res = INF;
		res = min(res, solve(l + 1, r) - a[l]);
		res = min(res, solve(l, r - 1) - a[r]);
	}

	dp[l][r] = res;

	return res;
}

signed main() {
	ll x;

	cin >> n;

	REP(i, n) {
		cin >> x;
		a.push_back(x);
	}

	cout << solve(0, n - 1) << endl;
}

Measured memory_bytes: 141312
#include<iostream>
#include<string.h>
#include<vector>
#include<list>
#include<stdio.h>
#include<math.h>
#include<iomanip>
#include<map>
#include<stack>
#include<queue>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define debug(x) cout << "debug " << x << endl;
using namespace std;

int main(){
    string str;
    while(cin >> str){
        int n, ans = 0;
        string ring;
        cin >> n;
        rep(i, n){
            cin >> ring;
            ring+= ring;
            rep(j, 10){
                bool check = true;
                rep(k, str.size()){
                    if(str[k] != ring[j + k]){
                        check = false;
                        break;
                    }
                }
                if(check){
                    ans++;
                    break;
                }
            }
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 1208
#include<iostream>
#include<cstdio>
#define MAX 100000
#define D 2147483647
using namespace std;

int A[MAX];
int n;

void update(int x, int y){
    A[x] = y;
}

int find(int x, int y){
    if(x <= y){
        int min = A[x];
        for(int i = x; i <= y; i++){
            if(A[i] < min) min = A[i];
        }
        return min;
    }
    else return D;
}
int main(){
    int q,com,x,y;
    scanf("%d %d",&n,&q);
    for(int i = 0; i < n; i++) A[i] = D;
    for(int i = 0; i < q; i++){
        scanf("%d %d %d",&com,&x,&y);
        if(com == 0) update(x,y);
        else if(com == 1)printf("%d\n",find(x,y));
        else break;
    }
    return 0;
}


Measured memory_bytes: 3604
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
using namespace std;
int N;
vector<int> L;
int main(){
  cin >> N;
  L.resize(N);

  for(int i=0;i<N;i++){
    cin >> L[i];
  }

  sort(L.begin(),L.end());
  int largest = L[N-1];
  L.pop_back();
  int sum = accumulate(L.begin(),L.end(),0);
  if(largest < sum){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {

	var A, B, T int
	fmt.Scanf("%d %d %d", &A, &B, &T)

	var sum int
	for i := 1; i <= T; i++ {
		if i%A == 0 {
			sum += B
		}
	}

	fmt.Println(sum)
}


Measured memory_bytes: 1832
#include <stdio.h>

int main(void){
  int a,b,_a,_b,x,i;
  long int y;
  while(scanf("%d %d",&a,&b) != EOF){
    _a = a;
    _b = b;
    x = 1;
    for(i=2;i<(a/2+1)&&i<(b/2+1);i++){
      while(_a%i==0 && _b%i==0){
        _a /= i;
        _b /= i;
        x *= i;
      }
    }
    y = a / x * b;
    printf("%d %ld\n",x,y);
    }
    return 0;
}

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

int main(){
	map<char, int> m;
	string w;
	cin >> w;
	rep(i, w.size()){
		m[w[i]]++;
	}
	for(auto mn : m){
		if(mn.second % 2 == 1){
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<string> vs;
#define fo(i, a, b) for (int i = a; i < b; i++)
#define re(i, n) fo(i, 0, n)
#define pb push_back
#define all(s) s.begin(), s.end()
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
int main()
{
  ll x;
  cin >> x;

  bool c = true;
  ll a = 100, i = 1;
  while(c) {
    a = floor(a * 1.01);
    if(x <= a) {
      cout << i << endl;
      c = false;
    }
    i++;
  }

  return 0;
}


Measured memory_bytes: 3744
import java.util.Scanner;

public class Main {

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

		// ラベル入力・ダイスの生成
		Dice dice1 = new Dice(CreateIntLabel(sc.nextLine()));
		Dice dice2 = new Dice(CreateIntLabel(sc.nextLine()));

		// 同じダイスであるか判定・出力
		if (DiceComparison(dice1, dice2)) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
		sc.close();
	}

	// ラベル配列の生成
	public static int[] CreateIntLabel(String str) {
		String[] input=str.split("[\\s]+");
		int[] label = new int[input.length];
		for (int i = 0; i < input.length; i++) {
			label[i] = Integer.parseInt(input[i]);
		}
		return label;
	}

	// 2つのダイスが同じかを判定
	public static boolean DiceComparison(Dice dice1, Dice dice2) {
		// ダイス1の0番目と同じラベルをダイス2から探す
		for (int i = 0; i < dice2.label.length; i++) {
			if (dice1.label[0] == dice2.label[i]) {

				// 側面4つの並びが同じか判定
				if (ComparisonNumberSequence(dice1.getCorrespondingAspectsLabels(0),
						dice2.getCorrespondingAspectsLabels(i))) {
					return true;
				}
			}
		}
		return false;

	}

	// 配列(ダイスの側面4つ)を2つを受け取り、同じ順序ができるか判定
	public static boolean ComparisonNumberSequence(int[] array1, int[] array2) {
		// 0番目の値が同じになるまでarray2を回転させる
		while (array1[0] != array2[0]) {
			int work = array2[0];
			for (int i = 1; i < array2.length; i++) {
				array2[i - 1] = array2[i];
			}
			array2[array2.length - 1] = work;
		}

		// 内容が同じになったかを見る
		for (int i = 0; i < array1.length; i++) {
			if (array1[i] != array2[i]) {
				return false;
			}
		}
		return true;

	}

	static class Dice {
		// 回転方向上にある4つの面の添え字、対応する右の面の添え字
		enum Direction {
			Roll			(new int[] { 0, 1, 5, 4 }, 2),
			Pitch			(new int[] { 0, 3, 5, 2 }, 1),
			Yaw				(new int[] { 4, 2, 1, 3 }, 5),
			ReverseRoll	(new int[] { 0, 4, 5, 1 }, 3),
			ReversePitch	(new int[] { 0, 2, 5, 3 }, 4),
			ReverseYaw		(new int[] { 4, 3, 1, 2 }, 0);

			// 回転軸方向の4つの面
			private int[] Rotat;
			// 回転軸方向に対応する右の面
			private int rightNum;

			Direction(int[] nums, int num) {
				this.Rotat = nums;
				this.rightNum = num;
			}
		}

		// ラベル
		int[] label;

		// コンストラクタ
		Dice(int[] label) {
			this.label = label;
		}

		// 右の面の添え字を受け取り、回転方向の4面の添え字配列を返す
		int[] getCorrespondingAspects(int num) {
			for (Direction dir : Direction.values()) {
				if (dir.rightNum == num) {
					return dir.Rotat;
				}
			}
			return null;
		}

		// 右の面の添え字を受け取り、回転方向の4面のラベル配列を返す
		int[] getCorrespondingAspectsLabels(int num) {
			int[] pointers = getCorrespondingAspects(num);
			int[] labels = new int[pointers.length];
			for (int i = 0; i < labels.length; i++) {
				labels[i] = this.label[pointers[i]];
			}
			return labels;

		}

	}

}



Measured memory_bytes: 26380
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

#define rep(inc, bgn, end) for (int inc = bgn; inc < end; ++inc)
#define repe(inc, bgn, end) for (int inc = bgn; inc <= end; ++inc)

using ll = long long;
using namespace std;

int main() {
    int n;  // 3*10e5;
    cin >> n;

    string s;
    cin >> s;
    // west
    vector<int> west(n, 0);
    rep(i, 0, n - 1) {
        if (s[i] == 'W') {
            west[i + 1] = west[i] + 1;
        } else {
            west[i + 1] = west[i];
        }
    }

    // east
    vector<int> east(n, 0);
    rep(j, 0, n - 1) {
        int i = n - 1 - j;
        if (s[i] == 'E') {
            east[i - 1] = east[i] + 1;
        } else {
            east[i - 1] = east[i];
        }
    }

    int ans = n;
    rep(i, 0, n) {
        ans = min(ans, west[i] + east[i]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep2(i, m, n) for(int i=int(m); i<int(n); ++i)
#define drep2(i, m, n) for(int i=int(m-1); i>=int(n); --i)
#define rep(i, n) rep2(i, 0, n)
#define drep(i, n) drep2(i, n, 0)
#define all(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using Vbo = vector<bool>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using VVbo = vector<Vbo>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << " "; return os; }
template<typename T> inline int count_between(vector<T> &a, T l, T r) { return lower_bound(all(a), r) - lower_bound(all(a), l); } // [l, r)
inline int Log2(ll x) { int k; for (k = 0; x > 0; ++k) x >>= 1; return k; } // number of binary digits
const int INF  = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS   = 1e-10;
const int MOD  = int(1e9)+7;


int main() {
  string s, t; cin >> s >> t;
  int m = s.size();
  int n = t.size();

  VV dp(m+1, V(n+1));
  vector<vector<P>> pre(m+1, vector<P>(n+1));

  rep(i, m) rep(j, n) {
    if (s[i] == t[j]) {
      dp[i+1][j+1] = dp[i][j] + 1;
      pre[i+1][j+1] = P(i, j);
    }
    else if (dp[i][j+1] > dp[i+1][j]) {
      dp[i+1][j+1] = dp[i][j+1];
      pre[i+1][j+1] = P(i, j+1);
    }
    else {
      dp[i+1][j+1] = dp[i+1][j];
      pre[i+1][j+1] = P(i+1, j);
    }
  }

  string ans = "";
  int i = m, j = n;
  while (i || j) {
    int i2, j2;
    tie(i2, j2) = pre[i][j];
    if (i2 == i-1 && j2 == j-1) ans = s[i2] + ans;
    i = i2;
    j = j2;
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 105984
#include<bits/stdc++.h>
#include<cstring>
using namespace std;
int main()
{
    int n,k,sum=0;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    for(int i=0;i<k;i++)
    {
        sum+=a[i];
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 3628
while True:
      n, m = map(int, raw_input().split())
      if n == 0 and m == 0:
            break
      p = [ 1 for i in range(n) ]
      pn = n; count = 0
      while pn > 1:
            for i in range(n):
                  if p[i] == 1:
                        count += 1
                        if count == m:
                              if p.count(1) > 1:
                                    p[i] = 0
                                    pn -= 1
                                    count = 0
      print p.index(1)+1

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

typedef pair<int,int> P;
typedef pair<P,int> PI;

//BEGIN CUT HERE
template<typename T>
struct BIT{
  int n;
  vector<T> bit;
  //1-indexed
  BIT():n(-1){}
  BIT(int n_,T d):n(n_),bit(n_+1,d){}

  //bit[i]は長さはiの最後のbit分で、スタートはそれ以外のbit 合計でちょうどiまでの情報
  //最後のbitが表す物をk,それ以外のbitが表す物をlとするとbit[i]=(l,l+k]でl+k=i

  T sum(int i){
    T s=bit[0];
    for(int x=i;x>0;x-=(x&-x))//x&-x:(xの最後のbit) 上の言葉でxをl+kからlにしてる
      s+=bit[x];
    return s;
  }

  void add(int i,T a){
    if(i==0) return;
    for(int x=i;x<=n;x+=(x&-x))//k,l+kは自明に増える lは増えない(lとkの間に0が出来ない)
      bit[x]+=a;
  }

  int lower_bound(int w){//w以上となる最小の場所を返す 単調性を仮定してる(bit[i]>=0)
    if(w<=0) return 0;
    int x=0,r=1;
    while(r<n) r<<=1;
    for(int k=r;k>0;k>>=1){//xに2のべき乗を大きい方から足せるなら足すだけ
      if(x+k<=n&&bit[x+k]<w){
        w-=bit[x+k];
        x+=k;
      }
    }
    return x+1;//xはw未満を満たす最大の場所なので1大きい値を返す
  }

  T sum0(int i){
    return sum(i+1);
  }

  void add0(int i,T a){
    add(i+1,a);
  }

  T query(int l,int r){
    return sum(r-1)-sum(l-1);
  }

  T query0(int l,int r){
    return sum(r)-sum(l);
  }
};
//END CUT HERE

signed main(){
  int n,q;cin>>n>>q;
  vector<int> c(523456,-1);
  vector<P> v;
  BIT<int> bit(523456,0);
  for(int i=1;i<=n;i++){
    int a;cin>>a;
    if(~c[a]){
      v.push_back(P(c[a],i));
      bit.add(i,1);
    }
    c[a]=i;
  }
  sort(v.begin(),v.end());
  vector<PI> lr(q);
  for(int i=0;i<q;i++){
    int l,r;cin>>l>>r;
    lr[i]=PI(P(l,r+1),i);
  }
  sort(lr.begin(),lr.end());
  vector<int> ans(q);
  int now=0;
  for(int i=0;i<q;i++){
    while(now<v.size()&&v[now].first<lr[i].first.first)bit.add(v[now++].second,-1);
    ans[lr[i].second]=lr[i].first.second-lr[i].first.first-bit.sum(lr[i].first.second-1);
  }
  for(int p:ans)cout<<p<<endl;
}


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

int main(){
  int n,m;
  cin>>n>>m;
  vector<int>a(n);
  int c=0;
  long long sum=0;
  
  for(int i=0;i<n;i++){
    cin >> a.at(i);
    sum += a.at(i);
  }
  
  for(int i=0;i<n;i++){
    if(a.at(i)>=sum/(4.0*m)){
      c++;
    }
  }
  if(c>=m)
    cout <<"Yes"<<endl;
  else
    cout <<"No"<<endl;
}


Measured memory_bytes: 3632
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output


def chkprint(*args):
    names = {id(v): k for k, v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg), '???')+' = '+repr(arg) for arg in args))

# Binary converter


def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]

# --------------------------------------------


dp = None


def main():
    R = int(input())

    if R < 1200:
        print("ABC")
    elif R < 2800:
        print("ARC")
    else:
        print("AGC")


main()


Measured memory_bytes: 5396
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		long a = Long.parseLong(sc.next());
		long b = Long.parseLong(sc.next());
		long sum = 0;
		long from = Long.parseLong(sc.next());
		long to = Long.parseLong(sc.next());
		sum += (a*(to - from) < b) ? a*(to - from) : b;
		for(int i = 0; i < n - 2; i++) {
			from = to;
			to = Long.parseLong(sc.next());
			sum += (a*(to - from) < b) ? a*(to - from) : b;
		}
		System.out.println(String.valueOf(sum));
	}
}

Measured memory_bytes: 31112
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#define mp make_pair

using namespace std;
const int MAXN = 2e5 + 10;
bool can[3010][3010];




pair <int, int> ans;
int main() {
  int a, b, c, d, e, f;
  cin >> a >> b >> c >> d >> e >> f;
  can[0][0] = true;
  for (int mass = 0; mass <= f; mass++) {
    for (int sugar = 0; sugar <= f; sugar++) {
      if (can[mass][sugar]) {
        int water = mass - sugar;

        if (water >= 0 && 1ll * water * e  >= sugar * 100ll && mass <= f) {

          if (sugar * ans.first  >= ans.second * mass) {
            ans = mp(mass, sugar);

            //cout << mass << ' ' << sugar << " -> " << 100.0 * sugar / mass << endl;
          }
        }
        
        if (mass + 100 * a <= f) {
          can[mass + 100 * a][sugar] = true;
        }
        if (mass + 100 * b <= f) {
          can[mass + 100 * b][sugar] = true;
        }
        if (mass + c <= f) {
          can[mass + c][sugar + c] = true;
        }
        if (mass + d <= f) {
          can[mass + d][sugar + d] = true;
        }
      }
    }
  }
  cout << ans.first   << ' ' << ans.second << endl;
  return 0;
}


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

int main() {
    int r, c, a[100][100];
    int sum = 0, rsum[100] = {0}, csum[100] = {0};
    cin >> r >> c;

    for (int i=0; i<r; i++) {
        for (int j=0; j<c; j++) {
            cin >> a[i][j];
            sum = sum + a[i][j];
            rsum[i] = rsum[i] + a[i][j];
            csum[j] = csum[j] + a[i][j];

            cout << a[i][j] << " ";
        }
        cout << rsum[i] << endl;
    }

    for (int i=0; i<c; i++)
        cout << csum[i] << " ";
    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <cstring>
#include <deque>

using namespace std;

#define INF 1e+9

int f[10][10];
int visited[10][10];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};
int w,h;
int gy,gx;
int sy,sx;

struct state{
    int y;
    int x;
    int hp;
    int t;

    state(){}
    state(int _y, int _x, int _hp, int _t):y(_y), x(_x), hp(_hp), t(_t){}
};

int solve(){
    memset(visited, -1, sizeof(visited));
    deque<state> q;
    state st;
    int ny, nx;
    q.push_back(state(sy,sx,6,0));
    visited[sy][sx] = 6;

    while(!q.empty()){
        st = q.front();
        q.pop_front();

        if(st.y == gy && st.x == gx){
            return st.t;
        }

        if(st.hp == 1) continue;

        for(int i=0;i<4;i++){
            ny = st.y + dy[i];
            nx = st.x + dx[i];

            if(f[ny][nx] == 0) continue;

            if(visited[ny][nx] < st.hp){
                visited[ny][nx] = st.hp;
                if(f[ny][nx] == 4){
                    q.push_back(state(ny,nx,6,st.t+1));
                }else{
                    q.push_back(state(ny,nx,st.hp-1,st.t+1));
                }
            }
        }
    }
    return -1;
}

int main(){
    while(cin >> w >> h){
        if((w|h) == 0) break;

        for(int i=1;i<=h;i++){
            for(int j=1;j<=w;j++){
                cin >> f[i][j];
                if(f[i][j] == 3){
                    gy = i;
                    gx = j;
                }else if(f[i][j] == 2){
                    sy = i;
                    sx = j;
                }
            }
        }
        int ret= solve();

        cout << ret << endl;
    }
}

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

using namespace std;

int main()
{

    string s;
    cin >> s;
    if(s[0] == 'A')
    {
        int C = 0;
        for(int i=2; i<s.size()-1; i++)
        {
            if(s[i] == 'C')
            {
                C++;
            }
        }
        if(C == 1)
        {
            int upper = 0;
            for(int i=1; i<s.size(); i++)
            {
                if(isupper(s[i]))
                {
                    upper++;
                }
            }
            if(upper == 1)
            {
                cout << "AC";
            }
            else
            {
                cout << "WA";
            }
        }
        else
        {
            cout << "WA";
        }
    }
    else
    {
        cout << "WA";
    }
    return 0;

}


Measured memory_bytes: 256
var
	n,i,x,y:Longint;
	a,b,c,d:int64;
begin
	read(n);
	a:=1;
	b:=1;
	for i:=1 to n do begin
		read(x,y);
		c:=(a-1)div x+1;
		d:=(b-1)div y+1;
		if c<d then c:=d;
		a:=c*x;
		b:=c*y;
	end;
	writeln(a+b);
end.


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

# AtCoder Grand Contest 031
# Problem C: Differ by 1 Bit

N, A, B = [int(t) for t in input().split()]

def grayCode(n):
    """nビットGrayコードの生成器"""
    for v in range(2 ** n):
        yield v ^ (v >> 1)

def grayCodeEnding(b, n):
    """0で始まりbで終わるnビットGrayコードの生成器"""
    code = list(grayCode(n))
    l = len(code)
    p = code.index(b)  # bの出現位置
    assert p % 2 == 1  # bの重みは奇数なので奇数番目に現れる

    # 両端から交互にyield
    q = 0
    while q != p:
        yield code[q]
        if q % 2 == 0:
            q = l - 1 - q
        else:
            q += 1 if q < p else -1

    # 残りを線形にyield
    q = l - 1 - q
    d = 1 if q < p else -1
    for i in range(q + d, p + d, d):
        yield code[i]

def weight(v):
    """vをNビット2進表記したときの1の個数"""
    return sum(1 for k in range(N) if (v & (1 << k)) != 0)

# 0 からB ^ A への系列を求めるのと本質的に同じ.
B ^= A

# Bの重みが偶数なら, 長さ 2 ** N の系列は存在しない.
if weight(B) % 2 == 0:
    print('NO')
    exit()

print('YES')
code = [A ^ c for c in grayCodeEnding(B, N)]
print(' '.join(str(c) for c in code))

Measured memory_bytes: 17308
use std::vec::Vec;
use std::cmp::*;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

fn main() {
    let (l, r) = {
      let v: Vec<usize> = read_vec();
      (v[0], v[1])
    };

    if r - l + 1 >= 2019 {
      println!("{}", 0);
      return;
    }
    let mut ans = 2019;
    for i in l..r {
      for j in i+1..r+1 {
        ans = min(ans, (i * j) % 2019);
      }
    }

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


Measured memory_bytes: 4352
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define IFOR(i, m, n) for(ll i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
/* テンプレートここまで */
void yes(){
  cout << "Alice" << endl;
  exit(0);
}

void no(){
  cout << "Bob" << endl;
  exit(0);
}

void draw(){
  cout << "Draw" << endl;
  exit(0);
}

int main() {
  ll a,b; cin >> a >> b;
  if(a==b) draw();
  if(a==1) yes();
  if(b==1) no();
  if(a>b) yes();
  else if(a<b) no();
}

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

int main(void){
    long int n, a[5];
    scanf("%ld %ld %ld %ld %ld %ld", &n, &a[0], &a[1], &a[2], &a[3], &a[4]);
    long int min = a[0];
    for(int i = 1;i < 5;i++){
        if(min > a[i])min = a[i];
    }
    if(n % min == 0)printf("%ld\n", n/min + 4);
    else printf("%ld\n", n/min + 5);
    return 0;
}

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

/* 繰り返し自乗法. */
int modPow(long long a, long long n, long long p) {
	if (n == 0) return 1; // 0乗にも対応する場合.
	if (n == 1) return a % p;
	if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;
	long long t = modPow(a, n / 2, p);
	return (t * t) % p;
}

signed main() {
 //   cout << "aaa" << endl;
    int N;
    cin >> N;
    vector<int> A(N);
    rep (i, N) {
        int a;
        cin >> A[i];
    }
    sort(A.begin(), A.end());
    bool ret = true;
    rep (i, N-1) {
        if (A[i] == A[i+1]) {
            ret = false;
            break;
        }
    }

    if (ret == true) cout << "YES" << endl;
    else            cout << "NO"  << endl;

}

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

using namespace std;

void swap(int *x,int *y)
{
    int temp=*x;
    *x=*y;
    *y=temp;
}

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

    int x,y,z;
    cin>>x>>y>>z;

    swap(&x,&y);
    swap(&x,&z);

    cout<<x<<" "<<y<<" "<<z;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define N (1<<17)
using namespace std;
typedef long long ll;

class RMQ{
public:
  ll n,dat[2*N-1];

  //?????????
  RMQ(){n=N;memset(dat,0,sizeof(dat));}
  
  //k???????????????a????????´
  void update(int k,ll a){
    k+=n-1;
    dat[k]=a;
    while(k>0){
      k=(k-1)/2;
      dat[k]=min(dat[k*2+1],dat[k*2+2]);
    }
  }

  //[a,b)???????°????????±???????
  //query(a,b,0,0,n)
  ll query(int a,int b,int k=0,int l=0,int r=N){
    if(r==-1) r=n;
    if(r<=a||b<=l)return 0;
    if(a<=l&&r<=b)return dat[k];
    else{
      ll v1=query(a,b,k*2+1,l,(l+r)/2);
      ll vr=query(a,b,k*2+2,(l+r)/2,r);
      return min(v1,vr);
    }
  }
};


ll x[N];
int main(){  
  ll n;
  cin>>n;
  RMQ rmq;
  for(int i=1;i<=n;i++) cin>>x[i];

  ll sum=n*(1+n)/2,cost=0;  
  for(int i=1;i<=n;i++){
    ll mx=-rmq.query(1,x[i])+x[i];
    cost=max(cost,mx);
    rmq.update(x[i],-mx);
  }
  cout << sum-cost<<endl;
  return 0;
}

Measured memory_bytes: 5904
#include<bits/stdc++.h> 
using namespace std ;
typedef long long ll ;
#define int long long
const int maxn = 2e5 + 5 ;
int n ;
ll k , a[maxn] , b[maxn] ;
signed main()
{
	scanf("%d%lld" , &n , &k) ;
	for(int i = 1 ; i <= n ; i ++) scanf("%lld" , &a[i]) ;
	sort(a + 1 , a + n + 1) ;
	int x = 0 , y = 0 , z = 0 ;
	for(int i = 1 ; i <= n ; i ++) 	 if(a[i] < 0) x ++ ;
		else if(a[i] > 0) y ++ ;
		else z ++ ;
	if(x * y >= k)
	{
		ll l = -1e18 , r = -1 , ans = -1 ;
		while(l <= r)
		{
			ll mid = (l + r) / 2 ;
			int p = n - y + 1 ;
			ll sum = 0 ;
			for(int i = 1 ; i <= x ; i ++)
			{
				while(a[i] * a[p] > mid && p <= n) p ++ ;
				if(p <= n && a[i] * a[p] <= mid)  sum += n - p + 1 ;
			}
			if(sum >= k) r = mid - 1 , ans = mid ;
			else l = mid + 1 ;
		}
		printf("%lld\n" , ans) ;
	}
	else if(x * y + x * z + y * z + z * (z - 1) / 2 >= k) printf("0\n") ;
	else
	{
		k -= x * y + x * z + y * z + z * (z - 1) / 2 ;
		ll l = 1 , r = 1e18 , ans = 1e18 ;
		while(l <= r)
		{
			ll mid = (l + r) / 2 ;
			int nxt = x ;
			ll sum = 0 ;
			for(int i = 1 ; i <= x ; i ++) 	b[i] = -a[x - i + 1] ;
			for(int i = 1 ; i <= x ; i ++)
			{
				if(b[i] * b[i] <= mid) sum -- ;
				while(nxt >= 1 && b[nxt] * b[i] > mid) nxt -- ;
				if(nxt >= 1 && b[nxt] * b[i] <= mid) sum += nxt ;
			}
			nxt = y ;
			for(int i = 1 ; i <= y ; i ++) 			 b[i] = a[n - y + i] ;
			for(int i = 1 ; i <= y ; i ++)
			{
				if(b[i] * b[i] <= mid) sum -- ;
				while(nxt >= 1 && b[nxt] * b[i] > mid) nxt -- ;
				if(nxt >= 1 && b[nxt] * b[i] <= mid) sum += nxt ;
			}
			assert(sum % 2 == 0) ;
			if(sum / 2 >= k) r = mid - 1 , ans = mid ;
			else l = mid + 1 ;
		}
		printf("%lld\n" , ans) ;
	}
	return 0 ;
}



Measured memory_bytes: 3072
import java.io.*;
import java.util.*;
import java.util.function.*;

final class Solver {
	static final Solver INSTANCE = new Solver();

	void solve(Supplier<String> sc) {
		long N = Long.parseLong(sc.get());
		long min = Long.MAX_VALUE;
		for (long i = 1; i * i <= N; i++) {
			if (N % i != 0) continue;
			min = Math.min(min, i + N / i - 2);
		}
		System.out.println(min);
	}
}

class Main {
	public static void main(String... args) {
		System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		Solver.INSTANCE.solve(new Supplier<String>() {
			StringTokenizer line;

			public String get() {
				while (line == null || !line.hasMoreTokens()) try {
					line = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
				return line.nextToken();
			}
		});
		System.out.flush();
	}
}

Measured memory_bytes: 21460
#include <iostream>
#include <cstdlib> //abs(int x)
using namespace std;


int n;

int solve(int* A, int* B, int* C){
  int K[n+10][3];
  for (int i=0; i<n+10; i++){
    for (int j=0; j<3; j++){
      K[i][j] = 0;
    }
  }
  for (int i=0; i<3; i++){
    K[0][i] = 0;
  }
  K[1][0] = A[0], K[1][1] = B[0], K[1][2] = C[0];
  for (int i=2; i<n+1; i++){
    K[i][0] = max(K[i-1][1]+A[i-1],K[i-1][2]+A[i-1]);
    K[i][1] = max(K[i-1][0]+B[i-1],K[i-1][2]+B[i-1]);
    K[i][2] = max(K[i-1][0]+C[i-1],K[i-1][1]+C[i-1]);
  }
  return max(K[n][0], max(K[n][1], K[n][2]));
}

int main(){
  cin >> n;
  int A[n+10], B[n+10], C[n+10];
  for (int i=0; i<n; i++){
    cin >> A[i] >> B[i] >> C[i];
  }
  cout << solve(A, B, C) << endl;
  return 0;
}


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

int main() {
    int n, k;
    cin >> n >> k;
    int ans = 0;
    while(n){
        ans++;
        n /= k;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
    {
    	cin.tie(0);
        ios::sync_with_stdio(0);
    	int a,b;
    	cin>>a>>b;
    	if(a>b)cout<<a-b;
    	else cout<<0;
    	return 0;
    }




Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());

        int[] d = new int[n];
        for (int i = 0; i < n; i++) {
            d[i] = Integer.parseInt(sc.next());
        }

        Arrays.sort(d);

        System.out.println(d[n/2] - d[n/2 - 1]);
    }
}

Measured memory_bytes: 48024
#define _GLIBCXX_DEBUG//TLEの原因になるので注意！！！！！！！！！！！
#include<cmath>
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<int> arr;
stack<int> st;
queue<int> qu;
queue<pair<int,int> > qu2;
priority_queue<int> pq;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rep2(i,n) for(int i=1; i<=(int)(n); i++)
#define mins(x,y) x=min(x,y)
#define maxs(x,y) x=max(x,y)
typedef set<int> set_t;
typedef set<string> set_g;
typedef complex<double> xy_t;
static const int NIL = -1;
static const int INF = 1000000007;
#define mp make_pair
#define sz(x) int(x.xise())
#define mod 1000000007
#define reps(i,s,n) for(int i = s; i < n; i++)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
deque<int> deq;
#define fi first
#define se second
//#define int long long

//cerrはコメントアウトしなくても通る//ただしTLEを引き起こすことがある

ll N,M,H,W,K,Q,A,B;
string S;
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
//const ll INF = 1LL << 60;
//typedef pair<ll,ll> P;
typedef pair<int, int> P;

int h[100005];
int dp[100005];

int main(){
    int n;
    cin >> n;
    rep(i,n){
        cin >> h[i];
    }
    dp[0]=0;
    dp[1]=abs(h[1]-h[0]);
    reps(i,2,n){
        dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
    }
    /*
    rep(i,n){
        cerr<<dp[i]<<endl;
    }
    */
    cout<<dp[n-1]<<endl;
    return 0;
}




Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include<unordered_map>
#define M 1000000007
#define T 998244353
#define PI 3.142
#define ll long long

using namespace std;

int ab(int a, int b)
{
	if(a<b){
		return b-a;
	}
	return a-b;
}

int mini(int a, int b)
{
	if(a>b){
		return b;
	}
	return a;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, i;
	cin >> n;
	int a[n], cost[n];
	for(i=0; i<n; i++){
		cin >> a[i];
	}
	cost[n-1]=ab(a[n-1], a[n-2]);
	cost[n-2]=mini(cost[n-1]+ab(a[n-2], a[n-3]),ab(a[n-1], a[n-3]));
	for(i=n-3; i>0; i--){
		cost[i] = mini(cost[i+1]+ab(a[i], a[i-1]), cost[i+2]+ab(a[i-1], a[i+1]));
	}
	cout << cost[1] << endl;
	return 0;
}

Measured memory_bytes: 1024
s=input()
n=len(s)
q=s.count("?")
mod=10**9+7
def f(x,y,z):
  DP=[[0]*3 for _ in range(n+1)]
  for i in range(n):
    if s[i]==x:
      DP[i+1][0]=DP[i][0]+1
    else:
      DP[i+1][0]=DP[i][0]
    if s[i]==y:
      DP[i+1][1]=DP[i][1]+DP[i][0]
    else:
      DP[i+1][1]=DP[i][1]
    if s[i]==z:
      DP[i+1][2]=DP[i][2]+DP[i][1]
    else:
      DP[i+1][2]=DP[i][2]
  return DP[n][2]
ans=0
ans+=f("A","B","C")*3**q%mod
if q>=1:
  ans+=f("?","B","C")*3**(q-1)%mod
  ans+=f("A","?","C")*3**(q-1)%mod
  ans+=f("A","B","?")*3**(q-1)%mod
if q>=2:
  ans+=f("A","?","?")*3**(q-2)%mod
  ans+=f("?","B","?")*3**(q-2)%mod
  ans+=f("?","?","C")*3**(q-2)%mod
if q>=3:
  ans+=f("?","?","?")*3**(q-3)%mod
print(ans%mod)


Measured memory_bytes: 24504
#include <bits/stdc++.h>
#define sz(arr) (int)(arr).size()
#define rng(arr) arr.begin(), arr.end()
#define show(x) cout << #x << " = " << x << endl;
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
typedef long long int ll;

void _cin() {}
template <class Head, class... Tail>
void _cin(Head&& head, Tail&&... tail) {
  cin >> head;
  _cin(forward<Tail>(tail)...);
}

#define Cin(T, ...) \
  T __VA_ARGS__;    \
  _cin(__VA_ARGS__)

#define Cins(T, n, xs) \
  vector<T> xs(n);     \
  for (int i = 0; i < n; ++i) cin >> xs[i]

void Main();
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(15);
  Main();
  return 0;
}

void Main() {
  Cin(int, n);
  int ans = 0;
  rep(i, n) {
    Cin(int, a);
    ans += a - 1;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
  int A, B, C, X;
  int ans = 0;
  int a, b;
  
  scanf("%d %d %d %d", &A, &B, &C, &X);
  for(a = 0; a <= A; a++) {
    for(b = 0; b <= B; b++) {
      int ctmp = X - 500*a - 100*b;
      if(ctmp >= 0 && ctmp % 50 == 0 && ctmp / 50 <= C) ans++;
    }
  }
  printf("%d\n", ans);
  
  return 0;
}

Measured memory_bytes: 128
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args) {
		MyScanner sc = new MyScanner();
		int n = sc.nextInt();
		int r = sc.nextInt();
		int l = sc.nextInt();
		int d, t, x, time = 0, max = 0;
		int[] tv = new int[n];
		int[] score = new int[n];
		for (int i = 0; i < r; i++) {
			d = sc.nextInt() - 1;
			t = sc.nextInt();
			x = sc.nextInt();
			tv[max] += t - time;
			score[d] += x;
			if (x > 0) {
				if (score[max] < score[d]) {
					max = d;
				} else if (score[max] == score[d]) {
					max = min(max, d);
				}
			} else if (max == d) {
				max = 0;
				for (int j = 1; j < n; j++) {
					if (score[max] < score[j]) {
						max = j;
					}
				}
			}
			time = t;
		}
		tv[max] += l - time;
		int ans = 0;
		for (int i = 1; i < n; i++) {
			if (tv[ans] < tv[i]) {
				ans = i;
			}
		}
		System.out.println(ans + 1);
	}

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

class MyScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte()) {
			return buffer[ptr++];
		} else {
			return -1;
		}
	}

	private static boolean isPrintableChar(int c) {
		return '!' <= c && c <= '~';
	}

	private void skipUnprintable() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
			ptr++;
		}
	}

	public boolean hasNext() {
		skipUnprintable();
		return hasNextByte();
	}

	public int nextInt() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		int n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}
}

Measured memory_bytes: 35700
x = 0
while True:
    a, op, b = map(str, input(). split())
    
    if op == '+':
        print(int(a)+int(b))
    
    elif op == '-':
        print(int(a)-int(b))
    
    elif op == '*':
        print(int(a)*int(b))
        
    elif op == '/':
        print(int(a)//int(b))
        
    else:
        break
        
    x += 1


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

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

ll n,h;
ll a[100010],b[100010];
vector<ll> bs;

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

  cin>>n>>h;
  ll mxa=0;
  rep(i,n){
    cin>>a[i]>>b[i];
    maxch(mxa,a[i]);
    bs.push_back(b[i]);
  }
  sort(all(bs)); reverse(all(bs));

  ll sum=0,res=INF;
  rep(i,n+1){
    ll rest=h-sum;
    if(rest<=0)minch(res,i);
    else minch(res,i+((rest+mxa-1)/mxa));
    if(i<n)sum+=bs[i];
  }

  cout<<res<<endl;

  return 0;
}


Measured memory_bytes: 2676
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(ll i=0;i<(n);i++)
#define REP2(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(v) (v).begin(),(v).end()
#define INF 2e9
typedef long long ll;

int main()
{
    string s;
    ll k;
    cin>>s>>k;

    bool f=1;
    if(s.size()>=k){
        REP(i,k) if(s[i]!='1') f=0;
    }else f=0;
    if(f) cout<<'1'<<endl;
    else{
        REP(i,k){
            if(s[i]!='1'){
                cout<<s[i]<<endl;
                break;
            }
        }
    }

	return 0; 
}

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

using namespace std;

int main(void){
    int a, b, c;
    vector<int> v;
    cin>>a>>b>>c;
    v.push_back(a);
    v.push_back(b);
    v.push_back(c);

    if(v[0]<v[1]){
        int tmp;
        tmp = v[0];
        v[0] = v[1];
        v[1] = tmp;
    }
    if(v[1]<v[2]){
        int tmp;
        tmp = v[1];
        v[1] = v[2];
        v[2] = tmp;
    }
    if(v[0]<v[1]){
        int tmp;
        tmp = v[0];
        v[0] = v[1];
        v[1] = tmp;
    }
    if(v[0]<v[1]){
        int tmp;
        tmp = v[1];
        v[1] = v[2];
        v[2] = tmp;
    }

    int max;
    max = v[0]*10+v[1]+v[2];
    cout<<max<<endl;
    return 0;
}

Measured memory_bytes: 256
use std::io::{Read, stdin};
use std::str::FromStr;

fn main() {
    let s: String = read();
    let s: Vec<char> = s.as_str().chars().collect();
    let mut ai = 0;
    let mut zi = 0;
    for i in 0..s.len() {
        if s[i] == 'A' {
            ai = i;
            break;
        }
    }
    for i in 0..s.len() {
        if s[i] == 'Z' {
            zi = i;
        }
    }
    println!("{}", zi - ai + 1);
}


fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

Measured memory_bytes: 4352
n = int(input())
explored = set()
next = [[]for _ in range(n)]

from collections import deque
ls = []
for i in range(n-1):
    u, v, w= map(int, input().split())
    ls.append((u-1, v-1, w%2))
    next[u-1].append((v-1, w%2))
    next[v-1].append((u-1, w%2))

ans = [-1] * n

exploring = deque()
next_que = deque([0])
ans[0]=0
explored.add(0)
while next_que:
    i = next_que.popleft()
    exploring.extend(next[i])
    while exploring:
        a, b = exploring.popleft()
        ans[a] = (ans[i]+b)%2
        list = next[a]
        if a not in explored:
            next_que.append(a)
        explored.add(a)


print(*ans, end='\n')

Measured memory_bytes: 58872
# util functions

# debug
$debugFlag = ( ARGV[0] != nil )
p "==== DEBUG MODE ====" if $debugFlag

def pd(str)
  p str if $debugFlag
end

def printd(str)
  print str if $debugFlag
end

# input
inputs = []
lc = 0
while l = $stdin.gets do
  if false
    inputs << l.chomp.split(" ").map(&:to_s)
  else
    inputs << l.chomp.split(" ").map(&:to_i)
  end
  lc += 1
end

# input check
if $debugFlag
  p "--- INPUT (begin) ---"
  inputs.each do |l_i|
    p l_i
  end
  p "--- INPUT (end) ---"
  print "\n"
end


# body
if $debugFlag
end

nn = inputs[0][0]

ans = "No"
for i in 1..9
  ans = "Yes" if nn % i == 0 and nn/i <= 9
end

puts ans


Measured memory_bytes: 1788
import java.util.*;
	
	
	
	public class Main {
	
		public static void main(String[] args) {
			Scanner sc = new Scanner(System.in);
			String S = sc.next();
			
			S=S.replaceAll("eraser", "-");
			S=S.replaceAll("erase", "-");
			S=S.replaceAll("dreamer", "-");
			S=S.replaceAll("dream", "-");
			S=S.replaceAll("-", "");
			if (S.length() == 0) {
				System.out.println("YES");
			}else {
				System.out.println("NO");
			}
			
			sc.close();
			
		}
		
		
	}

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

int main(){
    string t;
    cin >> t;
    for(long i = 0; i < t.size(); i++){
        if(t[i] == '?'){
            t[i] = 'D';
        }
    }
    cout << t << endl;
    return 0;
}

Measured memory_bytes: 3752
#include<cstdio>
char s[200001];
int main(){
    scanf("%s",s);
    long long cnt=0;
    int possibleA=0;
    for(int i=0;s[i]!='\0';i++){
        if(s[i]=='A')possibleA++;
        else if(s[i]=='B'){
            if(s[i+1]=='\0')break;
            if(s[i+1]=='C'){
                cnt+=possibleA;
                i++;
            }else{
                possibleA=0;
            }
        }else{
            possibleA=0;
        }
    }
    printf("%lld\n",cnt);
    return 0;
}

Measured memory_bytes: 384