akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <map>
#include <algorithm>
#include <iterator>

using namespace std;

map<size_t, size_t> pos;

// ACACTACG
//1122233

void find_all_ac(const std::string& str) {
    size_t count{0};
    pos.insert(make_pair(0, 0));
    for (size_t i = 1; i < str.size(); ++i) {
        if (str[i-1] == 'A' && str[i] == 'C') {
            ++count;
            pos.insert(make_pair(i, count));
            continue;
        }
        pos.insert(make_pair(i, count));
    }
    pos.insert(make_pair(str.size(), count));
}

int main(int argc, char** argv) {
    size_t N, Q;
    string str;
    cin >> N >> Q;

    cin >> str;

    find_all_ac(str);

    for (int q = 0; q < Q; ++q) {
        size_t l, r;
        cin >> l >> r;

        auto it_l = pos.find(l-1);
        auto it_r = pos.find(r-1);

        cout << (it_r->second - it_l->second) << endl;
    }

    return 0;
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

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

    // start
    string s;
    cin >> s;
    cout << "2018/01/" << s.at(8) << s.at(9) << endl;
    // end

    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<utility>
#include<cmath>
#include<algorithm>

using namespace std;

typedef pair<int, int> P;

int cave_num[1000][1000];
bool is_prime[1000001];
P trans[1000001];
P dp[1000001];
int m;

void prime() {
	int p = 0;
	for (int i = 0; i <= 1000000; i++)is_prime[i] = true;
	is_prime[0] = is_prime[1] = false;
	for (int i = 2; i <= 1000000; i++) {
		if (is_prime[i]) {
			for (int j = 2 * i; j <= 1000000; j += i)is_prime[j] = false;
		}
	}
}

P dfs(int n) {
	if (dp[n].first != -1)return dp[n];
	int res1 = 0, res2 = 0;
	P now = trans[n];
	for (int i = -1; i <= 1; i++) {
		if (now.second + 1 > 999)break;
		if (now.first + i < 0 || now.first + i>999)continue;
		if (cave_num[now.first + i][now.second + 1] > m)continue;
		P next = dfs(cave_num[now.first + i][now.second + 1]);
		if (res1 <= next.first) {
			if (res1 == next.first) {
				res2 = max(res2, next.second);
			}
			else {
				res2 = next.second;
			}
			res1 = next.first;
		}
	}
	if (is_prime[n]) {
		if (res2 == 0)res2 = n;
		res1++;
	}
	return dp[n] = P(res1, res2);
}

void num() {
	int sx = 499, sy = 500;
	int x = 1; cave_num[sx][sy] = x; trans[x] = P(sx, sy);
	for (int i = 1; i <= 999; i++) {
		if (i % 2) {
			for (int j = 0; j < i; j++) {
				cave_num[++sx][sy] = ++x;
				trans[x] = P(sx, sy);
			}
			for (int j = 0; j < i; j++) {
				cave_num[sx][--sy] = ++x;
				trans[x] = P(sx, sy);
			}
		}
		else {
			for (int j = 0; j < i; j++) {
				cave_num[--sx][sy] = ++x;
				trans[x] = P(sx, sy);
			}
			for (int j = 0; j < i; j++) {
				cave_num[sx][++sy] = ++x;
				trans[x] = P(sx, sy);
			}
		}
	}
	for (int i = 0; i < 999; i++) {
		cave_num[--sx][sy] = ++x;
		trans[x] = P(sx, sy);
	}
}

int main() {
	int n;
	prime();
	num();
	while (scanf("%d %d", &m, &n), m) {
		for (int i = 0; i <= m; i++)dp[i] = P(-1, -1);
		P p = dfs(n);
		printf("%d %d\n", p.first, p.second);
	}
}

Measured memory_bytes: 23280
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class Program
{
    static void Main()
    {
        var NABCD = ReadLine().Split().Select(int.Parse).ToArray();
        var N = NABCD[0];
        var A = NABCD[1] - 1;
        var B = NABCD[2] - 1;
        var C = NABCD[3] - 1;
        var D = NABCD[4] - 1;
        var S = ReadLine();

        var ans = true;
        if (C < D)
        {
            if (S.IndexOf("##", A, C - A) != -1) ans = false;
            if (S.IndexOf("##", B, D - B) != -1) ans = false;
        }
        else
        {
            if (S.IndexOf("##", A, C - A) != -1) ans = false;
            if (S.IndexOf("##", B, D - B) != -1) ans = false;
            if (S.IndexOf("...", B - 1, D - B + 3) == -1) ans = false;
        }
        WriteLine(ans ? "Yes" : "No");
    }
}

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

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

    vector<int> a(N);
    for (int i = 0; i < N; i++)
        cin >> a.at(i);
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end()); // aの配列を大きい順に並べ替え

    int Alice = 0;
    int Bob = 0;
    int count = 0;
    for (int i = 0; i < N; i++) {
        switch (count) {
        case 0:
            Alice += a.at(i);
            count = 1;
            break;
        case 1:
            Bob += a.at(i);
            count = 0;
            break;
        }
    }
    int ans = Alice - Bob;
    cout << ans << endl;
}

Measured memory_bytes: 256
l,r = map(int,input().split())
a = l % 2019
b = r % 2019
if r - l >= 2019:
    ans = 0
else:
    if a<b:
        mi = 2019
        for i in range(a,b):
            for j in range(i+1,b+1):
                mi = min(mi,(i*j)%2019)
        ans = mi
    else:
        ans= 0
print(ans)


Measured memory_bytes: 3060
a,b=map(int,input().split())
a-=1
b-=1
print(40,100)
for i in range(10):
  for j in range(50):
    if a>0:
      a-=1
      print('#.',end='')
    else:
      print('##',end='')
  print('');
  print('####################################################################################################');
for i in range(10):
  print('....................................................................................................');
  for j in range(50):
    if b>0:
      b-=1
      print('#.',end='')
    else:
      print('..',end='')
  print('');

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


#define ll long long
#define pb push_back

#define loop(i, a, b) for(int i = (a); i < (b); i++)
#define loopb(i, a, b) for(int i = (a); i > (b); --i)

typedef pair <int,int> ii;
typedef vector <int> vi;
typedef vector <ii> vii;
typedef vector <ll> vl;

const int mod = 1e9+7;
const ll inf = 2e18+5;

//RUNNING SUMS METHOD

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   
    int n, d, a;
    cin>>n>>d>>a;
    vii monsters;
    loop(i,0,n){
        int x,h;
        cin>>x>>h;
        h=(h+a-1)/a; //ceil(h/a)
        monsters.emplace_back(x,h);
    }
    assert((int)monsters.size()==n);
    sort(monsters.begin(),monsters.end());

    ll running_sum =0;
    vi change(n+1,0);
    ll ans=0;
    loop(i,0,n){
        running_sum+=change[i];
       
        int x = monsters[i].second - running_sum;
        if(x<=0)
            continue;
        ans+=x;
        running_sum += x;
        int lo=i, hi=n-1, ok;
        while(lo<=hi){
            int mid=(lo+hi)/2;
            if(monsters[mid].first <= monsters[i].first + 2LL*d){
                ok=mid;
                lo = mid+1;
            }
            else
                hi = mid-1;

        }
        change[ok+1] -= x;    
        
    }
    cout<<ans;
    return 0;
}   


Measured memory_bytes: 2544
#include <bits/stdc++.h>
#include <iostream>
#include <math.h>
using namespace std;
int main() {
    int N, M;
    cin >> N >> M;
    map<int, int>d;
    for (int i=0; i<N; i++) {
        int K;
        cin >> K;
        for (int j=0; j<K; j++) {
            int num;
            cin >> num;
            if (d.count(num) > 0) {
                d[num] = d[num] + 1;
            } else {
                d[num] = 1;
            }
        }
    }

    int sum = 0;
    for (int i=1; i<=M; i++) {
        if (d[i] == N) {
            sum += 1;
        }
    }

    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0; i<n; i++)
typedef long long ll;
typedef long long unsigned int llu;
ll MOD = 1000000007;
ll INF = 1000000009;

/*

i番目の料理以外を食べてj分以内に完食するものの最大値を計算し、全探索
dp1[i][j]:1~iまでの料理を用いて、j分以内に完食するときの満足度の最大値
dp2[i][j]:i~nまでの料理を用いて、j分以内に完食するときの満足度の最大値

求める値は、max( dp1[i-1][t-1] + dp2[i+1][t-1] )
各dp1,dp2は、

dp1[i][j] = max(dp1[i-1][j], dp1[i-1][j-a[i]])
dp1[0][a[0]] = b[0]
k < a[0] : dp1[0][k] = 0
k > a[0] : dp1[0][k] = b[0]
dp2[i][j] = max(dp2[i+1][j], dp2[i+1][j-a[i]])
dp2[n-1][a[n-1]] = b[n-1]
k < a[n-1] : dp2[n-1][k] = 0
k > a[n-1] : dp2[n-1][k] = b[n-1]

*/

ll dp1[3010][3010];
ll dp2[3010][3010];

void solve(){
    int n,t;
    cin >> n >> t;
    vector<ll> a;
    vector<ll> b;
    rep(i,n){
        int a_,b_;
        cin >> a_ >> b_;
        a.push_back(a_);
        b.push_back(b_);
    }
    rep(i,3010){
        rep(j,3010){
            dp1[i][j]=0;
            dp2[i][j]=0;
        }
    }
    rep(i,n){
        rep(j,t){
            if(i==0){
                if(j>=a[i]) dp1[i][j]=b[i];
            }else{
                if(j<a[i]) dp1[i][j] = dp1[i-1][j];
                else dp1[i][j] = max(dp1[i-1][j], dp1[i-1][j-a[i]]+b[i]);
            }
            //cout << "i:" << i << ", j:" << j << ", dp1[i][j]:" << dp1[i][j] << endl;
        }
    }

    for(ll i=n-1; i>=0; i--){
        rep(j,t){
            if(i==n-1){
                if(j>=a[i]) dp2[i][j]=b[i];
            }else{
                if(j<a[i]) dp2[i][j] = dp2[i+1][j];
                else dp2[i][j] = max(dp2[i+1][j], dp2[i+1][j-a[i]]+b[i]);
            }
            //cout << "i:" << i << ", j:" << j << ", dp2[i][j]:" << dp2[i][j] << endl;
        }
    }

    ll ans = 0;
    rep(i,n){
        ll ans_tmp = 0;
        rep(j,t){
            if(i==0) ans_tmp = max(ans_tmp, dp2[i+1][t-j-1]+b[i]);
            else {
                if(i==n-1) ans_tmp = max(ans_tmp, dp1[i-1][j]+b[i]);
                else ans_tmp = max(ans_tmp, dp1[i-1][j]+dp2[i+1][t-j-1]+b[i]);
            }
        }
        //cout << i << " " << ans << endl;
        ans = max(ans,ans_tmp);

    }
    cout << ans << endl;
}

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


Measured memory_bytes: 141952
#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() {
     string s;
     cin >> s;
     if(s.at(2)==s.at(3) && s.at(4)==s.at(5)){
         cout << "Yes"<< '\n';
     } else{
         cout << "No"<< '\n';
     }
    }

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

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

  int ans = 100;
  for (int i = 0; i < 26; i ++) {
    int tmp = 0, cnt = 0;;
    for (int j = 0; j < s.size(); j ++) {
      if (s.at(j) == 'a' + i) {
        cnt = max(cnt, tmp);
        tmp = 0;
      } else {
        tmp ++;
      }
    }
    cnt = max(cnt, tmp);
    ans = min(ans, cnt);
  }

  cout << ans << endl;
}


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;

int main() {
  int n;
  cin >> n;
  vector<int> L(n);
  rep(i,n) cin >> L[i];
  sort(L.begin(), L.end());
  int ans = 0;
  rep(b,n) rep(a,b) {
    int ab = L[a] + L[b];
    int r = lower_bound(L.begin(), L.end(), ab) - L.begin();
    int l = b+1;
    ans += r-l;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3616
def main():
    n=list(map(int,list(input())[::-1]))+[0]
    nl=len(n)
    ans=0
    for i in range(nl-1):
        if n[i]>=6 or (n[i]==5 and n[i+1]>=5):
            n[i]=10-n[i]
            n[i+1]+=1
    print(sum(n))
      
if __name__ == '__main__':
    main()

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

int main(){
    int a, b, c;
    int tmp;
    cin >> a >> b >> c;
    
    if(a > b){
        tmp = a;
        a = b;
        b = tmp;
    }
    
    if(b > c){
        tmp = b;
        b = c;
        c = tmp;
    }
    
    if(a > b){
        tmp = a;
        a = b;
        b = tmp;
    }
    
    cout << a << " " << b << " " << c << endl;
}


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

using namespace std;

int solve(vector<vector<int>> &G, int S, int T) {
    int N = G.size();
    vector<int> dist(N,2e9);
    queue<pair<int,int>> Q;
    Q.push({S, 0});

    while(!Q.empty()) {
        auto q = Q.front(); Q.pop();
        int pos = q.first;
        int d   = q.second;

        if(dist[pos] <= d) continue;
        if(pos == T) return d/3;

        dist[pos] = d;

        for(auto v : G[pos]) {
            if(dist[v] > d + 1) {
                Q.push({v,d+1});
            }
        }
    }
    return -1;
}

int main() {
    int N,M; cin >> N >> M;
    
    vector<vector<int>> G(3*N);

    for(int i=0;i<M;i++) {
        int u,v; cin >> u >> v;
        u--; v--;
        G[u      ].push_back(v + N);
        G[u + N  ].push_back(v + 2*N);
        G[u + 2*N].push_back(v);
    }

    int S, T; cin >> S >> T;
    
    cout << solve(G, S-1, T-1) << endl;

    return 0;
}


Measured memory_bytes: 17792
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <utility>
#include <algorithm>

using namespace std;

vector<int> dx = {0, 1, 0, -1};
vector<int> dy = {1, 0, -1, 0};

template<typename T> 
void show(T a){
  for(auto i : a){ cout << i << " "; }
  cout << endl;
}
template<typename T> 
void showmatrix(T a){
  for(auto j: a){for(auto i : j){ cout << i; }cout << endl;}
  cout << endl;
}
void check(int i = 0){
  cout << "checkpoint:[" << i << "]" << endl;
}


int main(int argc, char *argv[]){
  ios::sync_with_stdio(false);
  cin.tie(NULL);

  int h, w, h1, w1;
  cin >> h >> w >> h1 >> w1;
  cout << (h-h1)*(w-w1) << endl;

}


Measured memory_bytes: 256
// /**
// *    author:  Dooloper
// *    created: 03.05.2020 20:39:41
// **/

// #include <iostream>
// #include <vector>
// #include <map>
// #include <string>
// #include <utility>
// #include <algorithm>
// #include <queue>
// #include <deque>
// #include <stack>


// using namespace std;
// typedef unsigned long long ll;

// int main() {
//     cin.tie(0);
//     int N;cin>>N;
//     int K;cin>>K;
//     vector<int> human(N,0);
//     for(int i = 0 ;i < K; i++){
//         int d;cin>>d;
//         for(int j = 0; j < d; j++){
//             int keep;cin>>keep;
//             human.at(keep-1) = 1;
//         }
//     }
//     int cnt = 0;
//     for(int i:human){
//         if(i ==0)cnt++;
//     }

//     cout<<cnt<<endl;
// }
/**
*    author:  Dooloper
*    created: 03.05.2020 20:39:41
**/

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <utility>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>


using namespace std;
typedef unsigned long long ll;

int main() {
    cin.tie(0);
    string S;
    cin>>S;
    if(S=="ABC")cout<<"ARC"<<endl;
    else
    {
        cout<<"ABC"<<endl;
    }
    
    return 0;
}


Measured memory_bytes: 3592
#include <cstdio>
#include <cmath>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define S(x) scanf("%d",&x)
#define S2(x,y) scanf("%d%d",&x,&y)
#define P(x) printf("%d\n",x)
#define all(v) v.begin(),v.end()
#define FF first
#define SS second

typedef long long int LL;
typedef pair<int, int > pii;
typedef vector<int > vi;

LL sum(LL n, LL b) {
  LL res = 0;
  while(n) {
    res += n % b;
    n /= b;
  }
  return res;
}

int main() {
  LL n,s;
  scanf("%lld%lld",&n,&s);
  LL ans = -1;
  LL b;
  for(b = 2; b * b <= n; b++) {
    if(sum(n,b) == s) {
      cout << b << "\n";
      return 0;
    }
  }
  b = n / b;
  while(b) {
    LL y = n / b;
    LL x = (n / (b + 1)) + 1;
    if(x > y) {
      b--;
      continue;
    }
    LL d1 = n % y;
    LL d2 = n % x;
    LL req = s - b;
    LL mul = 1;
    if(x != y) {
      mul = n % x - (n % (x + 1));
    }
    if(req >= d1 && req <= d2 && (req - d1) % mul == 0) {
      LL a = (req - d1) / mul;
      ans = y - a;
      break;
    }
    b--;
  }
  if(ans == -1 && s == n) {
    ans = s + 1;
  }
  printf("%lld\n",ans);
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

int memo[212345] = {};
VL ans;
VL a;

void divisor(LL n){
    if(memo[n] %2 == 0 && a[n] == 0) return;
    if(memo[n] %2 == 1 && a[n] == 1) return;


    ans.eb(n);
    for(LL i = 1; i*i <= n; i++){
        if(n%i == 0){
            memo[i]++;
            if(i*i != n) memo[n/i]++;
        }
    }
}


signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    a.eb(0);
    REP(i,N){
        int tmp;
        cin >> tmp;
        a.eb(tmp);
    }
    for(LL i = N; i>0; i--){
        divisor(i);
    }
    cout << SZ(ans) << endl;
    if(SZ(ans) != 0){
        for(auto p : ans){
            cout << p << " ";
        }
        cout << endl;
    }

}


Measured memory_bytes: 5232
package main
 
import "fmt"
 
func main() {
  var n int
  fmt.Scan(&n)
  s := make([]int, n)
  for i := 0; i < n; i++ {
    fmt.Scan(&s[i])
  }
  var c int
  for i,v := range s {
    if ((i+1) % 2) == 1 && (v % 2) == 1 {
      c++
    }
  }
  fmt.Println(c)
}


Measured memory_bytes: 1776
@h=(<>!~$",sort{$b-$a}glob<>);for(1..$'){$v=$h[$i=1]>>1;$h[$i/2]=$h[$i]while$v<$h[$i+=$h[$i*=2]<$h[$i+1]];$h[$i/2]=$v}$\+=$_ for@h;print

Measured memory_bytes: 30204
#include <iostream>
#include <functional>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <queue>
// #include <prettyprint.hpp>
using namespace std;
typedef long long llong;
static const llong max_n = 100010;
static const llong mod = 1000000007;
vector<llong> result(max_n);

// template<typename T>
// void print_vec(vector<pair<llong, llong> vec){
//     cout << "[";
//     for(int i=0;i<vec.size();i++){
//         cout << vec[i] << " ";
//     }
//     cout << "]\n"
// }

inline llong power_mod(llong n, llong k){
    if(k > 1 && n > 1){
        llong ans = n;
        llong power_num = 1;
        vector<llong> power_result(k, 1);
        power_result[0] = ans;
        while(power_num * power_num <= k){
            
            ans = ans * ans;
            ans = (ans % mod);


            power_num = power_num * 2;
            power_result[power_num-1] = ans;

        }
        llong now_power_num = power_num;
        // printf("k=%lld, power num = %lld\n", k, now_power_num);

        while(power_num < k){
            // printf("%lld")
            // printf("now power num = %lld\n", now_power_num);
            now_power_num = now_power_num / 2;
            // printf("after now power num = %lld\n", now_power_num);
            llong num_times = (k - power_num) / now_power_num;
            for(llong i=0;i<num_times;i++){
                ans = ans * power_result[now_power_num-1];
                ans = (ans % mod);
            }

            power_num += now_power_num * num_times;
        }

        return ans;

        

    }else{
        return n;
    }

}


int main(){
    // int u, v;
    llong N, K;
    // bool updated = false;
    llong ans = 0;
    scanf("%lld %lld", &N, &K);

    for(llong i=K;i>=1;i--){
        llong all_num = power_mod(K/i, N);
        // printf("power all num of i=%lld: %lld\n", i, all_num);
        for(llong j=2;j<=K/i;j++){
            all_num = (all_num - result[i*j-1] + mod) % mod;
            // if(n_all_num < 0){
            //     printf("all num = %lld, r = %lld, i=%lld, j=%lld\n", all_num, result[i*j-1], i, j);
            //     exit(0);
            // }
            // all_num = n_all_num;
        }
        result[i-1] = all_num;
        // if(all_num < 0){
        //     printf("all num = %lld\n", all_num);
        //     exit(0);
        // }
        ans = ans + ((all_num * i) % mod);
        ans = (ans % mod);
    }

    printf("%lld\n", ans);
    // double limit = 1. / (double)(4 * M);



    return 0;

}

Measured memory_bytes: 4308
/**
 * C - Candies
 * https://atcoder.jp/contests/abc087/tasks/arc090_a
 * 
 * 解法
 * 
 **/
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> a11(N, 0);
    vector<int> a21(N, 0);
    vector<int> s11(N, 0);
    vector<int> s21(N, 0);
    for(int i=0; i<N; i++) cin >> a11[i];
    for(int i=0; i<N; i++) cin >> a21[i];
    for(int i=0; i<N; i++) {
        if(i==0) {
            s11[i] += a11[i];  
            s21[i] += a21[N-1-i];  
        } else {
            s11[i] += s11[i-1] + a11[i];
            s21[i] += s21[i-1] + a21[N-1-i];
        }
    }
    vector<int> sum(N, 0);
    for(int i=0; i<N; i++) {
        sum[i] = s11[i] + s21[N-1-i];
    }
    sort(sum.begin(), sum.end());
    cout << sum[N-1] << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;

int n;
int a[200000],b[200000];
struct T
{
    int num,fre;
}A[200000],B[200000];
int lenA,lenB;

void init()
{
    cin>>n;
    n/=2;
    for (int i=0; i<n; ++i)
        cin>>a[i]>>b[i];
}


void check(int a[200000],T A[200000],int &len)
{
    int flag[200000]={0};
    for (int i=0; i<n; ++i)
        flag[a[i]]++;
    for (int i=0; i<150000; ++i)
        if (flag[i])
        {
            A[len].fre=flag[i];
            A[len].num=i;
            len++;
        }
}

void work()
{
    check(a,A,lenA);
    check(b,B,lenB);
    sort(A,A+lenA,[](T a, T b){return a.fre>b.fre;});
    sort(B,B+lenB,[](T a, T b){return a.fre>b.fre;});
    //for (int i=0; i<lenA; ++i)
        //cout<<A[i].num<<' '<<A[i].fre<<endl;
    //for (int i=0; i<lenB; ++i)
        //cout<<B[i].num<<' '<<B[i].fre<<endl;
    if (A[0].num!=B[0].num)
    {
        cout<<n*2-A[0].fre-B[0].fre<<endl;return;
    }
    cout<<min(n*2-A[0].fre-B[1].fre,n*2-A[1].fre-B[0].fre);
}


int main()
{
    init();
    work();
    return 0;
}



Measured memory_bytes: 3840
#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(false);

    int a, b;

    cin >> a >> b;

    if (a > 12) {
        cout << b << endl;
    }
    else if (a >= 6 && a <= 12) {
        cout << b/2 << endl;
    }
    else {
        cout << 0 << endl;
    }

    return 0;
}

Measured memory_bytes: 256
N, W = map(int, input().split())
inf = 1 << 60
# dp[i][j] = i個目までの石を重さjで運んだときの価値の最大値
dp = [[-inf for j in range(W + 1)] for i in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    wi, vi = map(int, input().split())
    for w in range(0, W + 1):
        dp[i][w] = max(dp[i][w], dp[i - 1][w])
    for w in range(wi, W + 1):
        dp[i][w] = max(dp[i][w], dp[i - 1][w - wi] + vi)
    #print(dp[i])
ans = max(dp[N])
print(ans)


Measured memory_bytes: 171248
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


def main():
    N = int(input())
    D = list(map(int, input().split()))
    c = [0] * 13
    c[0] = 1
    for d in D:
        c[d] += 1
    if max(c) >= 3 or c[0] >= 2 or c[12] >= 2:
        print(0)
        return

    ans = 0
    # 2 ^ nの組み合わせの全列挙
    n = 11  # 0と12は選択の余地がない
    for b in range(2 ** n):
        a = [0]
        if c[12]:
            a.append(12)

        for i in range(n):
            d = i + 1
            if c[d] == 0:
                continue
            elif c[d] == 2:
                a += [d, 24 - d]
            elif b & 1 << i:
                a.append(d)
            else:
                a.append(24 - d)
        a.sort()
        mini = INF
        for i in range(len(a) - 1):
            mini = min(mini, abs(a[i] - a[i + 1]))
        mini = min(mini, abs(24 - a[-1]))

        ans = max(ans, mini)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3956
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.root = [-1]*(n+1)
		self.rank = [0]*(n+1)

	def find(self, x):
		if(self.root[x] < 0):
			return x
		else:
			self.root[x] = self.find(self.root[x])
			return self.root[x]
			
	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if(x == y):
			return 0
		elif(self.rank[x] > self.rank[y]):
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if(self.rank[x] == self.rank[y]):
				self.rank[y] += 1
	
	def f(self, x):
		return self.root[x] < 0
		
n,m,*l=map(int,open(0).read().split())
uf=UnionFind(n)
for i,j in zip(l[::3],l[1::3]):
	uf.unite(i,j)
print(sum(uf.f(i) for i in range(1,n+1)))

Measured memory_bytes: 32428
h, w = map(int, input().split())
mat = [input() for _ in range(h)]

dp = [[0]*w for _ in range(h)]
if mat[0][0] == "#":
    dp[0][0] = 1
for i in range(1, w):
    if mat[0][i] != mat[0][i-1] and mat[0][i] == "#":
        dp[0][i] = dp[0][i-1] + 1
    else:
        dp[0][i] = dp[0][i-1]
for j in range(1, h):
    if mat[j][0] != mat[j-1][0] and mat[j][0] == "#":
        dp[j][0] = dp[j-1][0] + 1
    else:
        dp[j][0] = dp[j-1][0]

for i in range(1, h):
    for j in range(1, w):
        ver = dp[i-1][j]
        hor = dp[i][j-1]
        if mat[i-1][j] != mat[i][j] and mat[i][j] == "#":
            ver += 1
        if mat[i][j-1] != mat[i][j] and mat[i][j] == "#":
            hor += 1
        dp[i][j] = min(ver, hor)
print(dp[h-1][w-1])


Measured memory_bytes: 3188
def judge(num):
  l = len(num)
  if N != l:
    return False

  for i in range(M):
    if int(num[s[i] - 1]) != c[i]:
      return False

  return True  

N, M = map(int, input().split())
s = []
c = []

for i in range(M):
  a, b = map(int, input().split())
  s.append(a)
  c.append(b)
  
for i in range(1000):
  if judge(str(i)):
    print(i)
    exit()
    
print(-1)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <numeric>
#include <string>
#include <cstring>
#include <list>
#include <unordered_set>
#include <tuple>
#include <cmath>
#include <limits>
#include <type_traits>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <regex>
#include <random>
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define rep(i,n)for(ll i=0;i<n;++i)
#define exout(x) printf("%.10f\n", x)
const double pi = acos(-1.0);
const ll MOD = 1000000007;
const ll INF = 1e10;
const ll MAX_N = 1010;

//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
	if (x == 0 || y == 0)return 0;
	return (x / gcd(x, y) * y);
}

ll c[20][20];
ll math[220][220];
ll number[11];
ll dp[20][20];

//long longしか使わない
//素数は1より大きい
int main() {
	ll h, w;
	cin >> h >> w;
	rep(i, 10) {
		rep(j, 10) {
			cin >> c[i][j];
		}
	}
	rep(i, 10) {
		rep(j, 10) {
			if (j == 1)continue;
			rep(k, 10) {
				if (j == k)continue;
				c[j][k] = min(c[j][k], c[j][i] + c[i][k]);
			}
		}
	}
	ll ans = 0;
	rep(i, h) {
		rep(j, w) {
			cin >> math[i][j];
			if (math[i][j] != 1 && math[i][j] != -1)ans += c[math[i][j]][1];
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 640
N, K = map(int, input().split())
Vs = list(map(int, input().split()))

ans = 0
for x in range(1, min(K, N)+1):
    for i in range(x+1):
        Ts = Vs[:i] + Vs[N-(x-i):]
        sumOut = sum(Ts)
        Ts.sort()

        for T in Ts[:K-x]:
            if T < 0:
                sumOut -= T
            else:
                break

        ans = max(ans, sumOut)

print(ans)


Measured memory_bytes: 40304
#include<stdio.h>
int main(void)
{
	int n,i,j,ss,pp,qq,rr,flg;
	int s[1001],p[1001],q[1001],r[1001];
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		for(i=0;i<n;i++) scanf("%d %d %d %d",&s[i],&p[i],&q[i],&r[i]);
		scanf("%d %d %d %d",&ss,&pp,&qq,&rr);
		flg=0;
		for(i=0;i<n;i++){
			if(p[i]<=ss&&q[i]<=pp&&r[i]<=qq&&p[i]*4+q[i]*9+r[i]*4<=rr){
				printf("%d\n",s[i]);
				flg=1;
			}
		}	
			if(flg==0) printf("NA\n");
	}
	return 0;
}	

Measured memory_bytes: 2720
import Data.Vector((!),fromList)
import Data.List
binarySearch :: Integral a => (a -> Bool) -> a -> a -> a
binarySearch pred ok ng
  | abs (ok-ng) <= 1 = ok
  | pred mid = binarySearch pred mid ng
  | otherwise = binarySearch pred ok mid
    where mid = (ok+ng) `div` 2

main = do
    n <- readLn :: IO Int
    l <-fromList . sort . map (read :: String -> Int) . words <$> getLine
    let list = [max 0 (right-left+1) |
           i <- [0 .. n - 3],
           let a = l ! i,
           j <- [i + 1 .. n - 2],
           let b = l ! j,
           -- condition :: l!k < a+b,abs (a-b) < l!k , j < k
           let left = binarySearch (\k -> abs (a-b) < l ! k) (n-1) j,
           let right = binarySearch (\k -> l ! k < a+b) 0 n
           ]
    print $ sum list
    return()

Measured memory_bytes: 5820
process.stdin.resume();
process.stdin.setEncoding('utf8');

var lines = [];
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
reader.on('line', (line) => {
  lines.push(line);
});
reader.on('close', () => {
  
  for(let i=0;i<lines.length;i++){
    const arr = lines[i].split(" ").map(Number)
    if(arr[0] == 0 && arr[1] == 0) break;
    if(arr[0] > arr[1]){
      const prev = arr[0];
      arr[0] = arr[1];
      arr[1] = prev;
    }
    console.log(arr.join(" "));
  }
});


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

int S[100001];
int T[50000];
int n;
int q;
int C;

void Binarysearch(int t){
    int mid = n/2;
    int right = n+1;
    int left = 0;
    while(left < right){
        if (S[mid] == t){
            C++;
            break;
        }
        else if (t < S[mid]){
            right = mid;
            mid = (left+mid)/2;
        }
        else{
            left = mid+1;
            mid = (right+mid)/2;
        }
    }
}

int main(){
    cin >> n;
    C = 0;
    for (int i = 0; i < n; i++){
        cin >> S[i];
    }
    cin >> q;
    for (int i = 0; i < n; i++){
        cin >> T[i];
    }
    for (int i = 0; i < q; i++){
        Binarysearch(T[i]);
    }
    cout << C << endl;
    
    return 0;
}


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

int ans[100005];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    int n = s.length();
    int r = 0, l = 0, poz;
    for (int i = 0; i < n; i++)
        if (s[i] == 'R')
        {
            r++;
            poz = i;
        }
        else
        {
            l++;
            if (s[i + 1] == 'R' || i + 1 >= n)
            {
                ans[poz] = ans[poz + 1] = (r + l) / 2;
                if (l % 2 != r % 2)
                    ans[poz + l % 2]++;
                r = l = 0;
            }
        }

    for (int i = 0; i < n; i++)
        cout << ans[i] << " ";

    return 0;
}

Measured memory_bytes: 1104
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

#define rep(i, a, b) for(auto (i)=a;i<b;i++)
#define list(i, N) for(auto (i)=0;i<N;i++)

typedef long long ll;
typedef vector <ll> vi;
typedef pair <ll, ll> pi;
#define mp make_pair
#define pb push_back
#define eb emplace_back

#define int ll
#define INF 1e18+5
#define mod 1000000007

template<class T>
T max(T a, T b, T c) {
    return max(a, max(b, c));
}

int32_t main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n; cin >> n;
    int a,b; cin >> a  >> b;
    int sum = a+b;
    int ans = n / sum;
    int diff = n - (ans * sum);
    ans *= a;
    //Now add the remaining amount of balls
    if(diff < a) ans += diff;
    else ans += a;
    cout << ans << "\n";

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
int rd(char c[]){
  int i, sz=0;
  for(;;){
    i = getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c[sz++] = i;
  for(;;){
    i = getchar_unlocked();
    if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
      break;
    }
    c[sz++] = i;
  }
  c[sz]='\0';
  return sz;
}
void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
char A[110], B[110], C[110];
int N;
int main(){
  int i, res=0;
  rd(N);
  rd(A);
  rd(B);
  rd(C);
  for(i=0;i<N;i++){
    if(A[i]==B[i] && B[i]==C[i]){
      continue;
    }
    if(A[i]==B[i] || B[i]==C[i] || C[i]==A[i]){
      res++;
      continue;
    }
    res += 2;
  }
  wt_L(res);
  putchar_unlocked('\n');
  return 0;
}
// cLay varsion 20180730-1

// --- original code ---
// int N;
// char A[110], B[110], C[110];
// {
//   int i, res = 0;
//   rd(N,A,B,C);
//   rep(i,N){
//     if(A[i]==B[i] && B[i]==C[i]) continue;
//     if(A[i]==B[i] || B[i]==C[i] || C[i]==A[i]){ res++; continue; }
//     res += 2;
//   }
//   wt(res);
// }


Measured memory_bytes: 256
#include <stdio.h>

int main(void){

    long A = 0;
    long B = 0;
    long K = 0;

    scanf("%ld %ld %ld", &A, &B, &K);

    if (A + B <= K){
        A = 0;
        B = 0; 

    } else {

        if (K <= A){
            A = A - K;

        } else {
            B = B - K + A;
            A = 0;

        }
    }
    
    printf("%ld %ld", A, B);

    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
const ll INF=1e15+7;
const ll N = 102;
ll ans=0,n,t[N],m,p,x;

int main(){
	cin>>n;
	FOR(i,0,n){
		cin>>t[i+1];
		ans+=t[i+1];
	}
	cin>>m;
	FOR(i,0,m){
		cin>>p>>x;
		cout<<ans-t[p]+x<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		try(Scanner sc = new Scanner(System.in)){
			int n = sc.nextInt();
			System.out.println(Ryuka(n));
		}
	}
	static long Ryuka(int n) {
		long[] ans = new long[87];
		ans[0] = 2;
		ans[1] = 1;
		for(int i = 2;i <= n;i++) {
			ans[i] = ans[i-1] + ans[i-2];
		}
		return ans[n];
	}
}



Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
constexpr long long MOD = 1000000007;
using ll = long long;
int main() {
ll h,w;
cin >> h>> w;
char c[h][w];
for (ll i = 0; i < h;i++){
    for (ll j = 0; j < w;j++){
        cin >> c[i][j];
    }
}

for (ll i = 0; i < h; i++) {
    for (ll j = 0; j < w; j++) {
        cout << c[i][j];
    }
    cout << endl;
     for (ll j = 0; j < w; j++) {
        cout << c[i][j];
    }
    cout << endl;
}

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;

/*
*/

ll n;
vector<ll> v[100010],c[100010],d(100010);

void dijkstra(int root,vector<ll>& d,vector<ll> v[],vector<ll> c[],ll INF=1e18){
	queue<int> Q;
	rep(i,d.size())d[i]=INF;
	d[root]=0;
	Q.push(root);
	while(!Q.empty()){
		int p = Q.front();Q.pop();
		for(int i=0;i<v[p].size();i++){
			int q = v[p][i];
			ll cost=c[p][i];
			if(d[q]>d[p]+cost){
				d[q]=d[p]+cost;
				Q.push(q);
			}
		}
	}
}

void init(){
	cin>>n;
	rep(i,n-1){
		ll a,b,d;
		cin>>a>>b>>d;
		v[a].push_back(b);
		v[b].push_back(a);
		c[a].push_back(d%2);
		c[b].push_back(d%2);
	}
}

int main(void){
	init();
	dijkstra(1,d,v,c);
	reg(i,1,n)cout<<d[i]%2<<endl;
	return 0;
}

Measured memory_bytes: 13184
#include <iostream>
using namespace std;
int main(){
  int x;
  cin>>x;
  
  int a=2;
  while(a<=x){
    if(x==a){cout<<x<<endl;return 0;}
    if(x%a==0){break;}
    if(a%2==0){a++;}
    else{a+=2;}
  }
    
  while(x<1000001){
    if(x%2==0){x++;}
    else{x+=2;}
    a=2;
    while(a<=x){
      if(x==a){cout<<x<<endl;return 0;}
      if(x%a==0){break;}
      if(a%2==0){a++;}
      else{a+=2;}
    }
  }
  
  return 0;
    
}

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

int main() {
	int n, t, a;
	cin >> n >> t >> a;
	int h[1000], x;
	for (int i = 0; i < n; i++) {
		cin >> x;
		h[i] = 1000 * t - x * 6;
	}
	int min = 10e9;
	int keep = 0;
	for (int i = 0; i < n; i++) {
		if (min > abs(h[i] - 1000 * a)) {
			min = abs(h[i] - 1000 * a);
			keep = i;
		}
	}
	cout << keep + 1 << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
int h,w,i,j;
while(1){
scanf("%d %d",&h,&w);
if((h==0)&&(w==0))break;
for(i=0;i<h;i++){
for(j=0;j<w;j++){
printf("#");
}
printf("\n");
}
printf("\n");
}
return 0;
}

Measured memory_bytes: 572
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define REP(i, n) for(int i=0; i<=n; i++)
#define repr(i, n) for(int i=n; i>0; i--)
#define REPR(i, n) for(int i=n; i>=0; i--)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
template<class T> void puts(T x) { std::cout << x << std::endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int n;
ll x[110], y[110], h[110];

int main() {
    cin >> n;
    ll tx, ty, th;
    rep(i, n) {
        cin >> x[i] >> y[i] >> h[i];
        if (h[i] > 0) tx = x[i], ty = y[i], th = h[i];
    }

    for (int cx = 0; cx <= 100; cx++) {
        for (int cy = 0; cy <= 100; cy++) {
            bool flg = true;
            ll H = th + abs(tx-cx) + abs(ty-cy);
            H = max(H, 0ll);
            rep(i, n) {
                ll t = H - abs(cx - x[i]) - abs(cy - y[i]);
                t = max(t, 0ll);
                if (t != h[i]) flg = false;
            }
            if (flg) {
                printf("%d %d %lld\n", cx, cy, H);
                return 0;
            }
        }
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <string.h>
#include<iomanip>
#include <iterator>
#include <locale>

#define all(a) a.begin(),a.end()
#define VV(T) vector<vector< T > >
#define rep(i,N) for(int i = 0; i <N; i++)
#define repsg(i,s,g) for(int i = s; i <g; i++)
#define name(x) #x
using namespace std;

const int INF = INT_MAX;
const long long INFL = 1LL<<40;
const double PI = atan(1)*4;
const int MOD = pow(10,9)+7;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

typedef long long ll,LL;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pLL;


// vector入力
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec) is >> x;
    return is;
}
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){
    for(int i=0; i<vec.size(); i++){
        os << vec[i] << ( i+1 == vec.size() ? "" : " " );
    }
    return os;
}

const int N = 100005;
ll dp[N][4];

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

    if(s[0]=='?'){
        dp[0][0]=3;
        dp[0][1]=1;
    }else if(s[0]=='A'){
        dp[0][1]=1;
        dp[0][0]=1;
    }else{
        dp[0][0]=1;
    }
    
    
    repsg(i,1,s.size()){
        
        if(s[i]=='A'){
            dp[i][0]=dp[i-1][0];
            dp[i][1]=dp[i-1][0]+dp[i-1][1];
            dp[i][2]=dp[i-1][2];
            dp[i][3]=dp[i-1][3];
        }else if(s[i]=='B'){
            dp[i][0] =dp[i-1][0];
            dp[i][2] = dp[i-1][1]+dp[i-1][2];
            dp[i][3]=dp[i-1][3];
            dp[i][1]=dp[i-1][1];
        }else if(s[i]=='C'){
            dp[i][0] = dp[i-1][0];
            dp[i][3]=dp[i-1][2]+dp[i-1][3];
            dp[i][1]=dp[i-1][1];
            dp[i][2]=dp[i-1][2];
        }else{
            
            dp[i][0] = 3*dp[i-1][0];
            dp[i][1]=dp[i-1][0]+3*dp[i-1][1];
            dp[i][2] = dp[i-1][1]+3*dp[i-1][2];
            dp[i][3]=dp[i-1][2]+3*dp[i-1][3];
            
        }
        
        dp[i][0]%=MOD;
        dp[i][1]%=MOD;
        dp[i][2]%=MOD;
        dp[i][3]%=MOD;
        
    }
    
    cout<<dp[s.size()-1][3]%MOD<<endl;
    
    return 0;
}









Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
 
#define froop1(a,n) for(int i = a;i < n;i++)
#define froop2(a,n) for(int i = a;i > n;i--)
int main(){
	long long count = 0,N;
    string S;
  int I[10] = {0,0,0,0,0,0,1,1,1,2};
  int J[10] = {1,1,1,2,2,3,2,2,3,3};
  int K[10] = {2,3,4,3,4,4,3,4,4,4};
  cin >> N;
  vector<long long> c(5,0);
  froop1(0,N){
    cin >> S;
   if(S[0] == 'M')c.at(0)++;
     else if(S[0] == 'A')c.at(1)++;
    else if(S[0] == 'R')c.at(2)++;
    else if(S[0] == 'C')c.at(3)++;
    else if(S[0] == 'H') c.at(4)++;
  }
 froop1(0,10){
  count += c.at(I[i]) * c.at(J[i]) * c.at(K[i]); 
 }
  cout << count << endl;
return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();
        if (r < 1200) {
            System.out.println("ABC");
        } else if (r < 2800) {
            System.out.println("ARC");
        } else {
            System.out.println("AGC");
        }
    }

}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a[3];
    for(int i=0;i<3;i++)
     cin>>a[i];
     
     sort(a,a+3);
     
     cout<<a[0]+a[1];
    
     return 0;
}
     
   




Measured memory_bytes: 3636
#include <cstdio>
#include <vector>
using namespace std;

int main() {
	vector<int> A;
	int num_query; scanf("%d", &num_query);
	int command, tmp;
	for (int loop = 0; loop < num_query; loop++) {
		scanf("%d", &command);
		switch (command) {
        	case 0:
        		scanf("%d", &tmp);
        		A.push_back(tmp);
        		break;
        	case 1:
        		scanf("%d", &tmp);
        		printf("%d\n", A[tmp]);
        		break;
        	case 2:
        		A.pop_back();
        		break;
		}
	}
	return 0;
}


Measured memory_bytes: 3464
// Between a and b
#include <cmath>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

int main() {
    long long a, b, x, i;
    long long A, B;
    cin >> a >> b >> x;
    // if (a == b) {
    //     cout << a % x << endl;
    //     return 0;
    // }
    B = x * (b / x);
    if (a % x == 0) A = x * (a / x);
    else A = x * (a / x + 1);
    // cout << A << ' ' << B << endl;
    if (B >= A) cout << (B - A) / x + 1 << endl;
    else cout << 0 << endl;
    return 0;
}

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector<int> a(n,0),b(n,0),c(n,0);
    for(int i = 0; i < n; i++){
        cin >> a[i]>>b[i]>>c[i];
    }
    int hp[100010][3];
    hp[0][0] = a[0]; hp[0][1]= b[0]; hp[0][2] = c[0];
    for(int i = 1; i < n; i++){
        hp[i][0] = max(hp[i-1][1],hp[i-1][2]) + a[i]; 
        hp[i][1] = max(hp[i-1][0],hp[i-1][2]) + b[i]; 
        hp[i][2] = max(hp[i-1][1],hp[i-1][0]) + c[i]; 
    }
    int ns = max(hp[n-1][0],hp[n-1][1]);
    cout << max(ns,hp[n-1][2]) << endl;
    return 0;
}

Measured memory_bytes: 2560
#include<stdio.h>
int main(void){
	int  b[50],j,i,x,t,n;
	float k,k2,sum[50],max,syo,y,r;
	while(1){
		max=-1;
		scanf("%d",&n);
		if(n==0)break;
		scanf("%f",&y);
		for(i=0;i<n;i++){
			scanf("%d %f %d",&b[i],&r,&t);
//			printf("%d\n",r);
			if(t==1){
				syo=r/100;
				sum[i]=10000*(1+y*syo);
			}
			if(t==2){
				syo=r/100;
				k=1+syo;
				k2=k;
//				printf("%f\n",k);
				for(j=0;j<y-1;j++){
					k=k*k2;
				}
				sum[i]=10000*k;
			}
		}
		for(i=0;i<n;i++){
//			printf("%f\n",sum[i]);
			if(max<sum[i]){
				max=sum[i];
				x=b[i];
			}
		}
		printf("%d\n",x);
	}
	return 0;
}

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

#define vint vector<int>
#define vvint vector<vint>
#define sint stack<int>
#define qint queue<int>
#define rep(i, n) for(int i=0;i<(int)(n);i++) // 繰り返し処理
#define all(x) (x).begin(),(x).end() // 全体 こんな感じで使う→sort(all(a));
#define ct(a) cout << a << endl
#define iceil(a,b) (a+(b-1))/b //int ceil : 繰り上げの割り算 通常のceilではceil((7.0/2.0))のようにしなければならなかった。
#define ld long double
#define ll long long
#define ul unsigned long
vint CinLine(int N){vint v(N);for(int i=0;i<N;i++){cin >> v.at(i);}return v;}//cin line 連続でvectorに格納
void CoutLine(vint v){for(int i=0;i<v.size()-1;i++){cout<<v.at(i)<<" ";}cout << v.at(v.size()-1)<<endl;}

bool IsOver(ll a, ll b, ll lim){
    return (b > lim/a);
}

bool IsOverflow(ul a, ul b){
    ul x = b * a;
    return (x/a != b);
}

bool IsOver_ng(ll a, ll b){
    ll x = b * a;
    if(x/a != b){
        return true;
    }else{
        return false;
    }
}


void Main(){
    ul limit = pow(10,18);
    ul n;
    cin >> n;
    vector<ul> a(n);
    for(ul i = 0; i<n;i++){
        cin >> a[i];
        if(a[i] == 0){
            ct(0);
            return;
        }
    }
    ul ans = 1;
    for(ul i = 0; i < n; i++){
        //if(IsOver(ans,a[i], limit)){
        if(IsOverflow(ans,a[i])){
            ct(-1);
            return;
        }else {
            ans *= a[i];
            if ( ans > limit ){
                ct(-1);
                return;
            }
        }
    }
    ct(ans);
    return;
}

int main() {
    Main();
}


Measured memory_bytes: 4052