akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bits/stdc++.h>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define rep(X, Y) for (int(X) = 0; (X) < (Y); ++(X))
#define rrep(X, Y) for (int(X) = (Y)-1; (X) >= 0; --(X))
#define all(X) (X).begin(), (X).end()
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define print(x) cout << x << endl

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

void solve(long long N, long long x, std::vector<long long> a) {
  ll num = 0;
  rep(r, N - 1) {
    ll sum = a[r] + a[r + 1];
    if (sum > x) {
      num += sum - x;
      // キャンディがマイナス個になることはできない
      if (sum - x > a[r + 1]) {
        a[r] -= sum - x - a[r + 1];
        a[r + 1] = 0;
      } else {
        a[r + 1] -= sum - x;
      }
    }
  }
  print(num);
}

int main() {
  long long N;
  scanf("%lld", &N);
  long long x;
  scanf("%lld", &x);
  std::vector<long long> a(N);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &a[i]);
  }
  solve(N, x, std::move(a));
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>
#include <vector>
#include <tuple>

int main(void)
{
    int N;
    std::cin >> N;
    std::vector<std::tuple<int, int, int>> cp;
    for(int i=0; i<N; ++i)
    {
        int t, x, y;
        std::cin >> t >> x >> y;
        cp.push_back(std::make_tuple(t, x, y));
    }
    int t_end = std::get<0>(cp.back()) + 1;
    int x_c = 0;
    int y_c = 0;
    int ct = 0; // Current target
    for(int t=0; t<t_end; ++t)
    {
        // Check
        if(std::get<0>(cp[ct]) == t)
        {
            if(x_c == std::get<1>(cp[ct]) &&
               y_c == std::get<2>(cp[ct]))
            {
                if(ct+1 == cp.size())
                {
                    std::cout << "Yes" << std::endl;
                    return 0;
                }
                else
                    ++ct;
            }
            else
            {
                std::cout << "No" << std::endl;
                return 0;
            }
        }
        // Move
        if(std::get<1>(cp[ct]) < x_c)
            x_c -= 1;
        else if(std::get<1>(cp[ct]) > x_c)
            x_c += 1;
        else if(std::get<2>(cp[ct]) < y_c)
            y_c -= 1;
        else if(std::get<2>(cp[ct]) > y_c)
            y_c += 1;
        else
            x_c += 1;
    }
    return 0;
}


Measured memory_bytes: 1912
def main():
    S = input()
    K = int(input())
    a = list(S)
    cnt = 0
    if len(set(a))==1:
        cnt = (len(a)*K)//2
    elif a[0] != a[-1]:
        for l in range(len(a)-1):
            if a[l+1] == a[l]:
                a[l+1] = str(l)
                cnt += 1
        cnt *= K
    else:
        temp = 1
        temp_2 = 1
        i = 0
        while a[i] == a[i+1]:
            temp += 1
            i += 1
        j = len(a) - 1
        while a[j] == a[j-1]:
            temp_2 += 1
            j -= 1
        for k in range(i+1,j-1):
            if a[k+1] == a[k]:
                a[k+1] = str(k)
                cnt += 1
        cnt *= K
        cnt += temp//2
        cnt += temp_2//2
        temp_3 = (temp + temp_2)//2
        cnt += temp_3 * (K-1)


    print(cnt)

    
if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <iostream>
#include <memory>
#include <memory.h>
#include <cmath>
#include <fstream>
#include <cmath>
#include <numeric>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <sstream>
#include <cstdlib>
#include <cassert>
#include <cstdio>
#include <map>
#include <iomanip>
#include <list>
#include <cctype>
#include <algorithm>
#include <complex>
#define USE_MATH_DEFINES
using namespace std;

typedef complex<double> xy_t;
typedef pair<xy_t, xy_t> line;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> PP;
typedef pair<int, PP> PPP;
const int INF = 1 << 29;
const double EPS = 1E-10;

typedef pair<xy_t, bool> dat;

namespace std{
	bool operator < (const xy_t &a, const xy_t &b){
		return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
	}
}

double cross(const xy_t &a, const xy_t &b){
	return imag(conj(a) * b);
}

double dot(const xy_t &a, const xy_t &b){
	return real(conj(a)*b);
}

int ccw(xy_t a, xy_t b, xy_t c){
	b -= a; c -= a;
	if(cross(b, c) > 0) return 1;
	if(cross(b, c) < 0) return -1;
	if(dot(b, c) < 0) return +2;
	if(norm(b) < norm(c) ) return -2;
	return 0;
}

bool intersectSS(const line &s, const line &t){
	return ccw(s.first, s.second, t.first) * ccw(s.first, s.second, t.second) <= 0 &&
		ccw(t.first, t.second, s.first) * ccw(t.first, t.second, s.second) <= 0;
}

xy_t crosspoint(const line &l, const line &m){
	double a = cross(l.second - l.first, m.second - m.first);
	double b = cross(l.second - l.first, l.second - m.first);
	if(abs(a) < EPS && abs(b) < EPS) return m.first;
	if(abs(a) < EPS) assert(false);
	return m.first + b / a * (m.second - m.first);
}

int main(){
	int n;
	while(cin >> n && n){
		int ans = 0;
		for(int i = 2; i * (i + 1) / 2 <= n; i++){
			int n2 = n - (i - 1) * i / 2;
			if(n2 % i == 0) ans++;
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <numeric>
#include <sstream>
#include <iostream>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cfloat>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cctype>
#include <cstdio>
#include <cassert>
using namespace std;

#define EPS 1e-12
#define ull unsigned long long
#define ll long long
#define VI vector<ll>
#define PII pair<ll, ll> 
#define VVI vector<vector<ll> >
#define VVVI vector<vector<vector<ll>>>
#define VVVVI vector<vector<vector<vector<ll>>>>
#define REP(i,n) for(ll i=0,_n=(n);(i)<(ll)_n;++i)
#define REPR(i,n) for(ll i=(ll)(n)-1;0<=(i);--i)
#define RANGE(i,a,b) for(ll i=(ll)a,_b=(ll)(b);(i)<_b;++i)
#define RANGER(i,a,b) for(ll i=(ll)(b)-1,_a=(ll)(a);(_a)<=i;--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define ALLR(c) (c).rbegin(), (c).rend()
#define PB push_back
#define MP(a, b) make_pair(a, b)
#define POPCOUNT __builtin_popcount
#define POPCOUNTLL __builtin_popcountll
#define CLEAR(table, v) memset(table, v, sizeof(table));
#define UNIFORM_DOUBLE(a, b) (((b-a)*(double)rand()/RAND_MAX)+a) // [a, b) 
#define UNIFORM_LL(a, b) (ll)UNIFORM_DOUBLE(a, b) // [a, b) 
#define IN(v, lo, hi) ((lo)<=(v) && (v)<(hi))
#define DD(v) cout<<#v<<": "<<v<<endl
#define FI first
#define SE second
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const map<T0, T1>& v) { for( typename map<T0, T1>::const_iterator p = v.begin(); p!=v.end(); p++ ){os << p->first << ": " << p->second << " ";} return os; }
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const pair<T0, T1>& v) { os << v.first << ": " << v.second << " "; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << " "; } return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const set<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const deque<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<vector<T> >& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << endl; } return os; }
template<typename T>void maxUpdate(T& a, T b) {a = max(a, b);}
template<typename T>void minUpdate(T& a, T b) {a = min(a, b);}

#define MOD 1000000007LL
#define INF (1LL<<60)

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll N,M,W,H;
	string s;
	while(cin>>s) {
		s[0]++;
		cout<<s<<endl;
	}
	
	return 0;
}


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

int main() {
    char s[100001];
    scanf("%s", s);
    while(1) {
        long l = strlen(s);
        if (strcmp((s+l-5), "dream") == 0)
            s[l-5] = '\0';
        else if (strcmp((s+l-7), "dreamer") == 0)
            s[l-7] = '\0';
        else if (strcmp((s+l-5), "erase") == 0)
            s[l-5] = '\0';
        else if (strcmp((s+l-6), "eraser") == 0)
            s[l-6] = '\0';
        else 
            break;
    }
    if (strlen(s))
        puts("NO");
    else 
        puts("YES");
    return 0;
}


Measured memory_bytes: 256
/*!enjoy karo yaar!*/

//CF,CC,AtC,SPOJ: hp1999
//HE: hemant269
//HR: hemant2132

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

/*-----<Defines>-----*/
#define     int             long long int
#define     fast()          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)          begin(x),end(x)
#define     rz(x)           resize(x)
#define     asn(x,y)        assign(x,y)
#define     mem(a,b)        memset(a,b,sizeof(a))
#define     sz(x)           ((int)size(x))
#define     eb              emplace_back
#define     pb              push_back
#define     pf              push_front
#define     pob             pop_back
#define     pof             pop_front
#define     ins             insert
#define     vi              vector<int>
#define     pii             pair<int,int>
#define     mii             map<int,int>
#define     F               first
#define     S               second
#define     remax(a,b)      a=max(a,b)
#define     remin(a,b)      a=min(a,b)
#define     bitcount(x)     __builtin_popcountll(x)
#define     iceil(n,x)      (((n)-1)/(x)+1)
#define     flush           fflush(stdout)

using ull=unsigned long long;
using ll=long long;
using ld=long double;
/*-----</Defines>-----*/

/*-----<Debugging Stuff>-----*/
string to_string(char s)
{   string res="'''";res[1]=s;return res; }

string to_string(string s)
{   return '"'+s+'"'; }

string to_string(const char* s)
{   return to_string((string)s); }

string to_string(bool b)
{   return (b?"true":"false"); }

template<typename A, typename B>
string to_string(pair<A, B> p)
{   return "("+to_string(p.F)+", "+to_string(p.S)+")"; }

template<typename A>
string to_string(A v)
{
    bool first=1; string res="{";
    for(const auto &x:v)
    {
        if(!first)  res+=", ";
        first=0;
        res+=to_string(x);
    }
    res+="}";
    return res;
}

void debug() { cout<<"\n"; }
template<typename Head, typename... Tail>
void debug(Head H, Tail... T)
{
    cout<<" "<<to_string(H);
    debug(T...);
}

#define show(...) cout << "[" << #__VA_ARGS__ << "]:", debug(__VA_ARGS__)
/*-----</Debugging Stuff>-----*/

/*-----<Mod Operations>-----*/
const int M=1e9+7;
inline int add(int a,int b,int p=M){ a=a+b; if(a>=p) a-=p; return a; }
inline int sub(int a,int b,int p=M){ a=a-b; if(a<0) a+=p; return a; }
inline int mul(int a,int b,int p=M){ a=(a*1ll*b)%p; return a; }
/*-----</Mod Operations>-----*/

/*-----<Constants>-----*/
const ld pi=acos(-1),eps=1e-9;
const ll inf=1e18;
const int N=1;
/*-----</Constants>-----*/

void solve()
{
    int n;
    cin>>n;
    int x=iceil(n,1000);
    int ans=1000*x-n;
    cout<<ans;
}

int32_t main()
{
    fast();

    int t=1;
    //cin>>t;
    for(int z=1;z<=t;++z)
    {
        solve();
        //cout<<"\n";
    }

    return 0;
}



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

int main() {
int n;
cin>>n;
string s;
int ans=0;
int m=0;
cin>>s;
for (int i = 0; i < n; ++i) {
	if(s[i]=='I'){
		ans=ans+1;
		m=max(m,ans);
	}else{
		ans=ans-1;
		m=max(m,ans);
	}
}
cout<<m<<endl;
}


Measured memory_bytes: 384
using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp3
{
    class Program
    {
        static void Main(string[] args)
        {
            double[] number = Console.ReadLine().Split(' ').Select(double.Parse).ToArray();
            double a = number[0];
            double b = number[1];
            double C = number[2] * (Math.PI / 180);

            double S =  a * b * Math.Sin(C) / 2;

            double c = Math.Sqrt(Math.Pow(a, 2) + Math.Pow(b, 2) - 2 * a * b * Math.Cos(C));
            double L = a + b + c;

            double h = b * Math.Sin(C);


            Console.WriteLine($"{S}\n{L}\n{h}");
        }
    }
}


Measured memory_bytes: 18472
A,B,C,K = (int(i) for i in input().split())

sum = 0

if  A >= K:
    sum = A - (A - K)
    print(sum)
    
elif A < K:
    sum = A
    K = K - A
    
    if B >= K:
        
        print(sum)
        
    elif B < K:
        K = K - B
        sum = sum - (K)
        print(sum)
    

Measured memory_bytes: 9188
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		boolean[] arr = new boolean[n];
		for (int i = 0; i < m; i++) {
		    arr[sc.nextInt() - 1] = true;
		}
		int left = 0;
		int right = n - 1;
		int count = 0;
		while (left < right) {
		    while(left < n && arr[left]) {
		        left++;
		    }
		    while(right >= 0 && !arr[right]) {
		        right--;
		    }
		    if (left < right) {
		        count++;
		        left++;
		        right--;
		    }
		}
		System.out.println(count);
	}
}



Measured memory_bytes: 29380
#!/usr/bin/env python3
import sys


def solve(N: int, S: str):
    answer = 0
    
    for i in range(N-2):
        if S[i:i+3] == "ABC":
            answer +=1

    print(answer)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
import numpy as np
import itertools
import sys
sys.setrecursionlimit(10**9)


INF=10**18
def solve(N,C,D,colormap,new_colormap):
    ans = INF
    for j in range(len(new_colormap)):
        new_colors = new_colormap[j]
        res = 0
        for mod in range(3):
            for current_color in range(1,C+1):
                if current_color == 0: continue
                new_color = new_colors[mod]
                res += D[current_color-1][new_color-1] * colormap[mod][current_color]

        ans = min(res,ans)

    
    print(ans)

    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    D = [[int(next(tokens)) for _ in range(C)] for _ in range(C)]  # type: "List[List[int]]"
    c = [[int(next(tokens)) for _ in range(N)] for _ in range(N)]  # type: "List[List[int]]"


    colormap = np.zeros((3,C+1),dtype=int)
    for i in range(1,N+1):
        for j in range(1,N+1):
            k = i+j
            k %= 3
            colormap[k][c[i-1][j-1]] += 1
            

    new_color_comb = list(itertools.permutations(list(range(1,C+1)),3))
    solve(N, C, np.array(D), colormap, np.array(new_color_comb))



def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('solve', '(i8,i8,i8[:,:],i8[:,:],i8[:,:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    # cc_export()
    try:
        from my_module import solve
    except:
        cc_export()
        exit()

    main()



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

using namespace std;

int main(){
  int N;
  
  int a[110],b[110],c[110],d[110];
  
  cin >> N;
  
   vector<pair<int,int>> p1(N);
  
  vector<pair<int,int>> p2(N);
  
  for(int i=0;i<N;i++){
  cin >> a[i] >> b[i] ;
    
    p1[i] = make_pair(b[i],a[i]);
  }
  
  for(int i=0;i<N;i++){
    cin >> c[i] >> d[i] ;
    
    p2[i] = make_pair(c[i],d[i]);
  }
  
 sort(p1.begin(),p1.end(),greater<pair<int,int>>());
  
  sort(p2.begin(),p2.end());
  
  int ans = 0;
  
  for(int i=0;i<N;i++){
    
    for(int j=0;j<N;j++){
      
      if(p1[i].second<p2[j].first&&p1[i].first<p2[j].second){
        
        ans++;
        p2[j]=make_pair(-1e9,-1e9);
        
        break;
      }
    }
  }
  
  cout << ans << endl;
}


Measured memory_bytes: 256
import sys
def input():
	return sys.stdin.readline()[:-1]

n, m, q = map(int, input().split())
s = ["0"*(m+1)] + ["0" + input() for _ in range(n)]

block = [[0 for _ in range(m+1)] for _ in range(n+1)]
for i in range(1, n+1):
	for j in range(1, m+1):
		block[i][j] = block[i][j-1] + block[i-1][j] - block[i-1][j-1] + int(s[i][j])

def block_num(x1, y1, x2, y2):
	return block[x2][y2] - block[x1-1][y2] - block[x2][y1-1] + block[x1-1][y1-1]

edge_h = [[0 for _ in range(m)] for _ in range(n+1)]
edge_v = [[0 for _ in range(m+1)] for _ in range(n)]

for i in range(1, n+1):
	for j in range(1, m):
		edge_h[i][j] = edge_h[i][j-1] + edge_h[i-1][j] - edge_h[i-1][j-1] + (int(s[i][j]) + int(s[i][j+1]) == 2)

for i in range(1, n):
	for j in range(1, m+1):
		edge_v[i][j] = edge_v[i][j-1] + edge_v[i-1][j] - edge_v[i-1][j-1] + (int(s[i][j]) + int(s[i+1][j]) == 2)

def edge_num(x1, y1, x2, y2):
	h = edge_h[x2][y2-1] - edge_h[x1-1][y2-1] - edge_h[x2][y1-1] + edge_h[x1-1][y1-1]
	v = edge_v[x2-1][y2] - edge_v[x1-1][y2] - edge_v[x2-1][y1-1] + edge_v[x1-1][y1-1]
	return h+v

for _ in range(q):
	x1, y1, x2, y2 = map(int, input().split())
	b = block_num(x1, y1, x2, y2)
	e = edge_num(x1, y1, x2, y2)
	print(b-e)

Measured memory_bytes: 158856
#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <time.h>
#include <stdio.h>
#define int long long
using namespace std;
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
int mypow(int x, int y) {
	if (y == 0)return 1;
	if (y % 2)return mypow(x, y - 1)*x;
	else return mypow(x, y / 2)*mypow(x, y / 2);
}
int Max(int x, int y) {
	if (x > y)return x;
	else return y;
}
int Min(int x, int y) {
	if (x < y)return x;
	else return y;
}
/*ライブラリゾーン！！！！！！！！！！！！！！！*/
map<int, int >mp;
int n, d, m, t;
signed main(){
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> d;
		mp[d]++;
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> t;
		if (mp[t] != 0)mp[t]--;
		else {
			cout << "NO" << endl;
			goto end;
		}
	}
	cout << "YES" << endl;
end:;
	system("PAUSE");
	return 0;
}


Measured memory_bytes: 12928
using System;

public class Program
{
	public static void Main()
	{
		while (true)
		{
			int N = int.Parse(Console.ReadLine());
			if (N == 0)
			{
				return;
			}
			int temp = 0;
			int ans = 0;
			int min = 1;
			for (int i = 1; i < N; i++)
			{
				temp += i;
				if (temp > N)
				{
					while (temp > N)
					{
						temp -= min++;
					}
				}
				if (temp == N)
				{
					++ans;
				}
			}
			Console.WriteLine(ans);
		}
	}
}

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

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
#define dump(val) cerr << __LINE__ << ":\t" << #val << " = " << (val) << endl

using namespace std;

typedef long long int lli;

int main() {
    lli X, Y;
    cin >> X >> Y;
    if (X % Y == 0) {
        cout << -1 << endl;
    } else {
        cout << X << endl;
    }
    return 0;
}

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

using namespace std;

int main(void){
  string str; cin >> str;
  int i, j, counter = 0, flag = 1;
  i = 0; j = str.size() - 1;
  
  while(j > i){
    if(str[i] == str[j]){
      i++;
      j--;
    }else{
      if(str[i] == 'x'){
	i++;
	counter++;
      }else if(str[j] == 'x'){
	j--;
	counter++;
      }else{
	flag = 0;
	break;
      }

    }
  }
  
  if(flag){
    cout << counter << endl;
  }else{
    cout << -1 << endl;
  }
  return 0;

}
      
      

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define N 10000011

using namespace std;

int a[N];

int main()
{
    long long n,i,j,sum = 0;
    scanf("%lld",&n);
    for(i=1;i<=n;i++){
        for(j=1;;j++){
            if(i*j>n) break;
            a[i*j]++;
        }

    }
    for(i=1;i<=n;i++) sum = sum+(a[i]*i);
    printf("%lld",sum);
    return 0;
}


Measured memory_bytes: 42800
N, M = map(int, input().split())
A = [int(x) for x in input().split()]

f = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
A = sorted(A, reverse=True)

dp = [float('-inf')] * (N + 1)
dp[0] = 0
for i in range(N + 1):
    for a in A:
        if i - f[a] >= 0:
            dp[i] = max(dp[i], dp[i - f[a]] + 1)

ans = ''
num, digit = N, dp[N]
while num > 0:
    for a in A:
        i = num - f[a]
        if i >= 0 and dp[i] == digit - 1:
            ans += str(a)
            num -= f[a]
            digit -= 1
            break
print(ans)


Measured memory_bytes: 3420
#include <bits/stdc++.h>
#define endl '\n'
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
#define ll long long
using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    ll a,b,c;
    cin>>a>>b>>c;
    if(a+b+c>=22)
    cout<<"bust";
    else
    cout<<"win";
	

	return 0;
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
#include <cassert>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ok() puts(ok?"Yes":"No");
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<int, int>;
using vvi = vector<vi>;
using vii = vector<ii>;
using gt = greater<int>;
using minq = priority_queue<int, vector<int>, gt>;
using P = pair<ll,ll>;
const ll LINF = 1e18L + 1;
const int INF = 1e9 + 1;
//clang++ -std=c++11 -stdlib=libc++ 

int main() {
  int A,B,T; cin >> A>> B>> T;
  cout<<T/A * B << endl;
  return 0;
}

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

#define mem( arr, i ) fill( arr, arr + sizeof (arr), i )
#define MEM( arr, i ) memset( arr, i, sizeof (arr) )
#define Push push_back
#define Pair make_pair
typedef unsigned long long ull;
typedef long long lli;
typedef pair<int,int> pii;
typedef pair<lli,lli> pll;
typedef vector<int> vcI;
typedef vector<lli> vcL;
typedef vector<pii> vPI;
typedef vector<pll> vPL;
//typedef priority_queue<T> prior_S<T>;
//typedef priority_queue< T, vector<T>, greater<T> > prior_B<T>;
const double PI = 3.141592653589793;
const lli I_MAX = 1LL << 60;
const lli mod = 1000000007;


void precal() {

	return;
}

bool solve() {
	lli n = 1, q;
	string s;
	if ( cin >> n >> q );
	else return false;
	
	lli num;
	bool broke[ n+5 ];
	MEM( broke, false );
	
	for (int i = 0; i < q; ++i) {
		cin >> num;
		broke[num] = true;
	}
	
	vcL dp( n+5, 0 );
	dp[0] = 1;
	
	for (int i = 0; i <= n; ++i) {
		if ( broke[i] ) continue;
		
		dp[ i+1 ] += dp[i]; dp[ i+1 ] %= mod;
		dp[ i+2 ] += dp[i]; dp[ i+2 ] %= mod;
	}
	
	cout << ((dp[n]%mod)+mod)%mod << '\n';
	
	return true;
}

int main() {
	precal();
	int t = INT_MAX;
//	cin >> t;
	for (int i = 1; i <= t; ++i) {
//		printf("Case #%d: ", i );
		if ( !solve() ) break;
	}
	return 0;
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
const ll INF = 2147483647;
const ll LINF = 9223372036854775807;
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

int main() {
	int n, m; cin >> n >> m;
	int ev=m/2, od=(m+1)/2;
	for(int i=1;i<=ev;i++){
		cout << i << ' ' << 2*ev-i+2 << endl;
	}
	for(int i=1;i<=od;i++){
		cout << (ev==0?i:2*ev+1+i) << ' ' << (ev==0?i:2*ev+2)+2*od-i << endl;
	}
	return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <map>

using namespace std;

int getinc(map<int, int> *m, int i){
  if(m->find(i) != m->end()){
    return ((*m)[i]) + 1;
  }
  return 1;
}

int main(){
  int n = 0;
  map<int, int> a;
  int ans = 0;
  cin >> n ;
  while(n--){
    int i;
    cin >> i;
    a[i] = getinc(&a, i);
  }

  for(auto itr = a.begin(); itr != a.end(); ++itr) {
    if(itr->first <= itr->second)
      ans += itr->second - itr->first;
    else
      ans += itr->second;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 4736
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = []
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge.append((a, b, -c))
    node = [inf] * N
    node[0] = 0
    exist_minus_cycle = False
    for i in range(N):
        update = False
        for from_, to, cost in edge:
            node_to = node[from_] + cost
            if node_to < node[to]:
                update = True
                node[to] = node_to
                
        if not update:
            break
        elif i==N-1:
            exist_minus_cycle = True

    #どこで無限に更新されるか判定
    minus_cycle = set()
    if exist_minus_cycle:
        for i in range(N):
            for from_, to, cost in edge:
                node_to = node[from_] + cost
                if from_ in minus_cycle:
                    minus_cycle.add(to)
                if node_to < node[to]:
                    minus_cycle.add(from_)
                    minus_cycle.add(to)
                    node[to] = node_to
        
    if N-1 in minus_cycle :
        print("inf")
    else:
        print(-node[-1])

if __name__ == '__main__':
    main()

Measured memory_bytes: 43484
#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 = 1; i < n; i++)
#define P pair<int, int>
typedef long long ll;
const ll mod = 1e9+7;

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}

//繰り返し自乗法による累乗計算
//a**n
ll pow(ll a, ll n){
  if(n == 0) return 1;
  if(n%2 == 0){
    ll res = pow(a, n/2);
    return res * res;
  }
  return a * pow(a, n-1);
}
//繰り返し自乗法によるmod累乗計算
//a**n (mod)
ll modpow(ll a, ll n){
  if(n == 0) return 1;
  if(n%2 == 0){
    ll res = modpow(a, n/2);
    return res * res % mod;
  }
  return a * modpow(a, n-1) % mod;
}
//組み合わせ
//nCa
ll com(ll n, ll a){
  ll x = 1, y = 1;
  rep(i,a){
    x *= n-i;
    y *= i+1;
  }
  ll res = x / y;
  return res;
}
//組み合わせ(mod)
//nCa (mod)
ll modcom(ll n, ll a){
  ll x = 1, y = 1;
  rep(i, a){
    x = x * (n-i) % mod;
    y = y * (i+1) % mod;
  }
  ll ans = x * modpow(y, mod-2) % mod;
  return ans;
}
//gcd 最大公約数
ll gcd(ll x, ll y){
  if(x % y == 0) return y;
  return gcd(y, x%y);
}
//lcm 最小公倍数
ll lcm(ll x, ll y){
  return x * y / gcd(x, y);
}
//ngcd n個の最大公約数
ll ngcd(vector<ll> a){
  ll res;
  res = a[0];
  for(ll i = 1; i < a.size() && res != 1; i++) {
    res = gcd(a[i], res);
  }
  return res;
}
//nlcm n個の最小公倍数
ll nlcm(vector<ll> a) {
  ll res;
  res = a[0];
  for (ll i = 1; i < a.size(); i++) {
    res = lcm(res, a[i]);
  }
  return res;
}
// 素数判定
bool isprime(ll x){
  ll i;
  if(x < 2) return false;
  else if(x == 2) return true;
  if(x % 2 == 0) return false;
  for(i = 3; i*i <= x; i += 2){
    if(x % i == 0) return false;
  }
  return true;
}
// 桁和
ll digsum(ll x){
  ll res = 0;
  while(x > 0){
    res += x % 10;
    x /= 10;
  }
  return res;
}


int main(){
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if((abs(a-b) <= d && abs(b-c) <= d) || abs(a-c) <= d){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }


}






Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
B - Power Socket
https://atcoder.jp/contests/abc139/tasks/abc139_b

"""
import sys


def solve(A, B):
    total = 1
    used = 0
    while total < B:
        total += (A - 1)
        used += 1
    return used


def main(args):
    A, B = map(int, input().split())
    ans = solve(A, B)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


Measured memory_bytes: 3060
n, m = map(int, input().split())
abc = []

dist = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    dist[i][i] = 0

for _ in range(m):
    abc.append(list(map(int, input().split())))

for a, b, c in abc:
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])

ans = 0
for a, b, c in abc:
    if dist[a-1][b-1] < c:
        ans += 1

print(ans)

Measured memory_bytes: 3568
#include <iostream>
typedef long long ll;
using namespace std;
int main(){
  int N;
  cin >> N;
  ll l_0 = 2;
  ll l_1 = 1;
  for(int i=1; i<N; i++){
    ll l_2 = l_0 + l_1;
    l_0 = l_1;
    l_1 = l_2;
  }
  if(N==0) cout << l_0 << endl;
  else cout << l_1 << endl;
  
  return 0;
}

Measured memory_bytes: 256
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint
from statistics import mean,median,mode

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

def RI():
    return list(map(int,input().split()))

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input()) for _ in range(n) ]

ddict = defaultdict(lambda: 0)
# ddict = defaultdict(lambda: 1)
# ddict = defaultdict(lambda: int())
# ddict = defaultdict(lambda: list())
# ddict = defaultdict(lambda: float())

n = I()
a = RI()

for i in range(n):
    ddict[a[i]] += 1

ans = 0
for i in ddict:
    c = ddict[i]
    if c==i:
        pass
    elif c>i:
        ans += c - i
    elif c<i:
        ans += c

print(ans)

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

#define for_(i,a,b) for(int i=(a);i<(b);++i)

int sign(int x) { return x < 0 ? -1 : 1; }

int main() {
	int x, y;
	cin >> x >> y;
	
	if (y == 0) {
		if (x < 0) cout << abs(x) << endl;
		else cout << 1 + abs(x) << endl;
	} else if (sign(x) == sign(y)) {
		if (x < y) cout << y - x << endl;
		else cout << max(abs(y), abs(x)) - min(abs(y), abs(x)) + 2 << endl;
	} else {
		cout << 1 + max(abs(y), abs(x)) - min(abs(y), abs(x)) << endl;
	}
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
    int c=0, r=0, i, j=0, sum=0;  //???????¨????r??????//
    scanf("%d %d", &r, &c);
    int sheet[c+1][r+1];
    for(i=0 ;i<r ;i++){
        for(j=0 ; j<c ;j++){
            scanf("%d", &sheet[j][i]);
        }
    }
    for(i=0 ;i<r ;i++){
        sheet[c][i] = 0;
        for(j=0 ;j<c ;j++){
            sheet[c][i] += sheet[j][i];
        }
    }
    for(i=0 ;i<c ;i++){
        sheet[i][r] = 0;
        for(j=0 ;j<r ;j++){
            sheet[i][r] += sheet[i][j];
        }
    }
    for(i=0 ;i<r ;i++){
        sum += sheet[c][i];
    }
    sheet[c][r] = sum;
    for(i=0 ;i<r+1 ;i++){
        for(j=0 ;j<c+1 ;j++){
            if(j == c){
                printf("%d", sheet[j][i]);
                break;
            }
            printf("%d ", sheet[j][i]);
        }
        
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 0x3f3f3f3f
int h[100005];
int main()
{
    int n,k,hmax,hmin;
    scanf("%d%d",&n,&k);
    for(int i=0; i<n; i++)
        scanf("%d",&h[i]);
    sort(h,h+n);
    int mi=maxn;
    for(int i=n-1;i>=0;i--)
    {
        hmax=h[i];
        if(i-k+1<0)
            break;
        hmin=h[i-k+1];
        int num=hmax-hmin;
        mi=min(mi,num);
    }
    printf("%d\n",mi);
    return 0;
}

Measured memory_bytes: 640
# A - Kth Term
def main():
    orig = "1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51"
    seq = list(map(lambda s: s.strip(), orig.split(",")))
    K = int(input()) - 1
    print(seq[K])


if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
import sys
N = int(input())
A = list(map(int, input().split()))
c = 0
a = 1
while 2 ** a <= 1e9:
    for i in range(N):
        if A[i] % (2 ** a) != 0:
            print(c)
            sys.exit()
    c += 1
    a += 1
print(c)

Measured memory_bytes: 9188
#include <iostream>

int main() {
    using namespace std;

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

    int c = 0;
    for(int i = 0; i < N - 1; ) {
        int c_s = 0;
        for(int j = i; j < N; j++) {
            if(a[i] == a[j]) {
                c_s++;
            } else {
                i = j;
                c += c_s / 2;
                break;
            }

            if(j == N - 1) {
                i = j;
                c += c_s / 2;
            }
        }
    }

    cout << c << endl;
    return 0;
}


Measured memory_bytes: 256
import numpy as np
n, d = (int(i) for i in input().split())
xy = [[int(i) for i in input().split()] for i in range(n)]
ans = 0
for i in range(n):
    x = xy[i][0]
    y = xy[i][1]
    l = np.sqrt(x**2 + y**2)
    if l <= d:
        ans += 1
print(ans)

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

int main()
{
    long N,r=1,R=0,x=10;
    cin>>N;
    for(int i=1;i<=N;i++){
        if(i%x==0){
            r++;
            x*=10;
        }
        if(r%2!=0){
            R++;
        }
    }
    cout<<R<<endl;
}

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

typedef long long lli;
typedef pair<lli,lli> pll;
typedef vector<lli> vcL;
typedef vector<pll> vPL;


void solve() {
	string s, t;
	cin >> s >> t;
	
	int sz = s.size();
	bool flag = false;
	
	for (int i = 0; i < sz; ++i) {
		int cnt = 0;
		
		for (int j = 0; j < sz; ++j) {
			if ( s[ (i+j)%sz ] == t[j] ) {
				cnt++ ;
			}
		}
		
		if ( cnt == sz ) flag = true;
	}
	
	if ( flag ) cout << "Yes\n";
	else cout << "No\n";
}

int main() {
	int t = 1;
//	cin >> t;
	for (int i = 1; i <= t; ++i) {
		solve();
	}
	return 0;
}



Measured memory_bytes: 256
fun solve(S: String) {
    val atcgMap = mutableMapOf("A" to "T","T" to "A","C" to "G","G" to "C")
    println(atcgMap[S])
//    var ans = ""
//    if (S == "A") {
//        ans = "T"
//    } else if (S == "T") {
//        ans = "A"
//    } else if (S == "C") {
//        ans = "G"
//    } else if (S == "G") {
//        ans = "C"
//    }
//    println(ans)
}

fun main() {
    val S = readLine()!!
//    val N = readLine()!!.toInt()
//    val (N, M) = readLine()!!.split(" ").map { it.toInt() }
//    val A = readLine()!!.split(" ").map { it.toInt() }
    solve(S)
}

Measured memory_bytes: 34892
#include <bits/stdc++.h>
  
#define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort( (x).begin(),(x).end() )
#define REVERSE(x) reverse( (x).begin(),(x).end() )
#define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() )
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())
#define SHOW(x) cout << #x << " = " << x << endl
 
#define pb emplace_back
#define fi first
#define se second

using namespace std;
 
typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpl> gr;
typedef vector<vl> ml;
typedef vector<vd> md;
typedef vector<vi> mi;
 
const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ld EPS = 1e-8;
const ll MOD = 1e9+7;

template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> inline T sq( T a ){ return a * a; }
ll in(){ ll x; scanf( "%lld" , &x ); return x; }
 
// head

char cs[100010];
string stin(){ scanf( "%s" , cs ); return cs; }

string s;

int main(){

  s = stin();
  
  REP( i , SZ(s)-1 ){
    if( s[i] == s[i+1] ){
      cout << i+1 << " " << i+2 << endl;
      return 0;
    }
  }

  REP( i , SZ(s)-2 ){
    if( s[i] == s[i+2] ){
      cout << i+1 << " " << i+3 << endl;
      return 0;
    }
  }
  

  puts( "-1 -1" );

  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
 
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define ll long long
 
const int N=3e5+5,MAX=3e7,MOD=1e9+7;
 
using namespace std;

int n;
string a;
int main()
{
   	

    	cin>>a;

    	bool ok = true;
    	for(int i=0;a[i];i++){
        if (i%2==0 && a[i]=='L'){
            ok=false;
        }
        else if (i%2==1 && a[i]=='R'){
            ok=false;
        }
    }
    if (ok)
        printf("Yes\n");
    else
        printf("No\n");
 	


}


Measured memory_bytes: 256
"""
Writer: SPD_9X2
https://atcoder.jp/contests/code-festival-2017-quala/tasks/code_festival_2017_quala_d

dが奇数なら楽勝→2色でただの市松模様に塗れば終わり

dが偶数の時が問題

d = 2だったら

1 3 1 
 2 4 2
3 1 3
 4 2 4

みたいな感じで塗ってけばおｋ

斜めで　d/2ずつ12/34交互で、d/2こ連続して同じ数字を置けばいい(斜めの軸は合わせる)

→実装が面倒
→数学的に頑張る
"""

H,W,D = map(int,input().split())
sd = D//2

if D % 2 == 1:

    ans = [[""] * W for i in range(H)]

    for i in range(H):
        for j in range(W):

            if (i+j) % 2 == 0:
                ans[i][j] = "R"
            else:
                ans[i][j] = "Y"

    for i in ans:
        print ("".join(i))

else:

    ans = [[" "] * W for i in range(H)]

    for i in range(H):
        for j in range(W):

              if (i+j) % 2 == 0:
                  
                  if ((i+j)// D) % 2 == 0 and (((j-i)//D) % 2 == 0):
                      ans[i][j] = "R"
                  elif ((i+j)// D) % 2 == 1 and (((j-i)//D) % 2 == 0):
                      ans[i][j] = "Y"
                  elif ((i+j)// D) % 2 == 0 and (((j-i)//D) % 2 == 1):
                      ans[i][j] = "G"
                  else:
                      ans[i][j] = "B"

              else:
                  if ((i+j)// D) % 2 == 0 and (((j-i)//D) % 2 == 0):
                      ans[i][j] = "R"
                  elif ((i+j)// D) % 2 == 1 and (((j-i)//D) % 2 == 0):
                      ans[i][j] = "Y"
                  elif ((i+j)// D) % 2 == 0 and (((j-i)//D) % 2 == 1):
                      ans[i][j] = "G"
                  else:
                      ans[i][j] = "B"

    for i in ans:
        print ("".join(i))
                      
        

                      


Measured memory_bytes: 43828
N,Q = map(int,input().split())
S = input()

t = [0]*(N+1)

for i in range(N):
    t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)

for i in range(Q):
    l,r = map(int,input().split())
    print(t[r-1] - t[l-1])

Measured memory_bytes: 7748
#include<bits/stdc++.h>
using namespace std;
int main()
{
      long long t=0,n,c,d,f,g,h,i,j,k,l,a1,a2,a3,b1,b2,b3;
      string a;
      cin>>a;
      n=a.size();
      for(i=0;i<n;i++)t+=(a[i]-'0');
      if(t%9==0)cout<<"Yes"<<endl;
      else
        cout<<"No"<<endl;
      return 0;
}


Measured memory_bytes: 3728
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <cmath>
#include <iostream>
#include <stack>
#include <queue>

#define ll long long int
#define all(x) x.begin(), x.end()
#define MOD 998244353

using namespace std;

void solve()
{
    int k;
    string s;
    cin >> k >> s;

    for (int i = 0; i < s.size(); i++)
    {
        if (i >= k)
        {
            cout << "..." << endl;
            return;
        }
        cout << s[i];
    }
}

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

    int T = 1;
    //cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}



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

ll K;

bool J1(pair<int, int>P1, pair<int, int>P2) {
	return max(abs(P1.first - P2.first), abs(P1.second - P2.second)) == K;
}

pair<int, int> J2(pair<int, int>P1, pair<int, int>P2) {
	int tx = P2.first - P1.first;
	int ty = P2.second - P1.second;

	bool cx = 0, cy = 0;
	if (tx < 0)tx = -tx, cx = 1;
	if (ty < 0)ty = -ty, cy = 1;

	//K, ty - K;

	if ((abs(K) + abs(ty - K)) & 1)return { 14,INT32_MAX };
	if (ty - K > K)return { 14,INT32_MAX };
	if (K + K < tx)return { 14,INT32_MAX };

	tx = K;
	if (cx)tx = -tx;
	ty -= K;
	if (cy)ty = -ty;

	return { P1.first + tx,P1.second + ty };
}

pair<int, int> t45(int a, int b) {
	return { a + b,a - b };
}

pair<int, int> t315(int a, int b) {
	return { (a + b) / 2,(a - b) / 2 };
}

void say(pair<int, int> P) {
	cout << P.first << " " << P.second << endl;
}

int main() {
	ll N, M;

	cin >> K >> N >> M;
	int tr;
	if ((K & 1) == 0) {
		if ((N + M) & 1) {
			cout << -1 << endl;
			return 0;
		}
	}

	int X, Y;
	tie(X, Y) = t45(N, M);

	int acx = 1, acy = 1;
	if (X < 0)X = -X, acx = -1;
	if (Y < 0)Y = -Y, acy = -1;


	int kx = X / K;
	int ky = Y / K;

	int lx = kx * X, ly = ky * Y;

	int nx = 0, ny = 0;
	pair<int, int> P;
	queue<pair<int, int>> Q;
	while (1) {
		if (J1({ nx,ny }, { X,Y })) {
			Q.push({ X,Y });
			break;
		}
		P = J2({ nx,ny }, { X,Y });
		if (P.second != INT32_MAX) {
			Q.push(P);
			Q.push({ X,Y });
			break;
		}
		//cout << nx << " " << ny << endl;
		if (nx < X) {
			nx += K;
		}
		else {
			nx -= K;
		}

		if (ny < Y) {
			ny += K;
		}
		else {
			ny -= K;
		}

		if (nx == X && ny == Y) {
			Q.push({ X,Y });
			break;
		}

		Q.push({ nx,ny });
	}
	cout << Q.size() << endl;
	pair<int, int> A, B(0, 0);
	while (!Q.empty()) {
		A = t315(Q.front().first * acx, Q.front().second * acy);
		say(A);
		if (abs(A.first - B.first) + abs(A.second - B.second) != K) {
			cout << "NO" << endl;
			assert(0);
			return 0;
		}
		B = A;
		Q.pop();
	}
	return 0;
}

Measured memory_bytes: 4224
#include<stdio.h>
int main()
{
	int n, W;
	scanf("%d %d", &n, &W);
	int w[102];
	long long int v[102];
	int i, j;
	for (i = 0; i < n; i++)
		scanf("%d %lld", &w[i], &v[i]);
	long long int dp[100005];
	for (i = 0; i < 100005; i++)
		dp[i] = -1;
	dp[0] = 0;
	for (i = 0; i < n; i++)
		for (j = W - w[i]; j >= 0; j--)
			if (dp[j] >= 0 && dp[j + w[i]] < dp[j] + v[i])
				dp[j + w[i]] = dp[j] + v[i];
	long long int ans = 0;
	for (i = 0; i <= W; i++)
		if (ans < dp[i])
			ans = dp[i];
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 896
#include <stdio.h>

int main(){
    int N,x;
    scanf("%d",&N);
    int range[N];
    for(int i=0;i<N;i++){
        scanf("%d",&x);
        range[i]=x;
    }
    printf("%d",range[N-1]);
    for(int i=N-2;0<=i;i--){
        printf(" %d",range[i]);
    }
    printf("\n");
}


Measured memory_bytes: 2104
//#include "stdafx.h"
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <tuple>
#include <numeric>
#include <assert.h>
#include <functional>
#include <unordered_map>

using namespace std;

/*-----------------------------------------------------------------------------
　定義
 -------------------------------------------------------------------------------*/
#define REP(i, n)				for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n)			for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define INF						2e9
#define MOD						(1000 * 1000 * 1000 + 7)
#define Ceil(x, n)				(((((x))+((n)-1))/n))		/* Nの倍数に切り上げ割り算 */
#define CeilN(x, n)				(((((x))+((n)-1))/n)*n)		/* Nの倍数に切り上げ */
#define FloorN(x, n)			((x)-(x)%(n))				/* Nの倍数に切り下げ */
#define IsOdd(x)				(((x)&0x01UL) == 0x01UL)			
#define IsEven(x)				(!IsOdd((x)))						
#define ArrayLength(x)			(sizeof( x ) / sizeof( x[ 0 ]))
#define	MAX_QWORD				((QWORD)0xFFFFFFFFFFFFFFFF)
#define M_PI					3.14159265358979323846
typedef long long				ll;
typedef unsigned long long int	QWORD;
typedef pair<ll, ll>			P;

/*-----------------------------------------------------------------------------
　処理
 -------------------------------------------------------------------------------*/
/* baseを階乗した値を求める */
template<class T>
T power(int base, int powNum)
{
	T ans = 1;
	for (int i = 0; i < powNum; i++) {
		ans *= base;
	}
	return ans;
}

int main()
{
	int a, b, c, k;
	cin >> a >> b >> c >> k;

	int ans;
	int mul = power<int>(2, k);
	if (a < c && b < c) {
		ans = a + b + c * mul;
	} else if (a < b && c < b) {
		ans = a + b * mul + c;
	} else {
		ans = a * mul + b + c;
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 256