akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

int main()
{
    int N, Q;
    string S;

    cin >> N >> Q;
    cin >> S;

    int l[Q], r[Q];

    for (int i = 0; i < Q; i++)
    {
        cin >> l[i] >> r[i];
        l[i] = l[i] - 1;
        r[i] = r[i] - 1;
    }

    /*
    int count[Q];

    for (int i = 0; i < Q; i++)
    {
        count[i] = 0;
        for (int j = l[i] - 1; j < r[i] - 1; j++)
        {
            if ((S[j] == 'A') && (S[j + 1] == 'C'))
            {
                count[i]++;
            }
        }
        cout << count[i] << endl;
    }
    */

    int count[N];
    int tmp = 0;

    count[0] = 0;

    for (int i = 1; i < N; i++)
    {
        if ((S[i - 1] == 'A') && (S[i] == 'C'))
        {
            tmp++;
            count[i] = tmp;
        }else{
            count[i] = tmp;
        }
    }

    int ans;

    for (int i = 0; i < Q; i++)
    {
        ans = count[r[i]] - count[l[i]];
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 2240
from itertools import combinations
a,(n,d)=0,list(map(int,input().split()))
for i in [sum([abs(i[0][j]-i[1][j])**2for j in range(d)])**0.5for i in list(combinations([list(map(int,input().split()))for i in range(n)],2))]:
  if i.is_integer():a+=1
print(a)

Measured memory_bytes: 3060
#include <stdio.h>

int main(void)
{
  int n, a, b, c;
  scanf("%d %d %d %d", &n, &a, &b, &c);
  int l[n];
  for (int i = 0; i < n; i++) {
    scanf("%d", &l[i]);
  }
  int ans = 10000;
  for (int i = 0; i < (1U << (n * 2)); i++) {
    int mp = 0;
    int bamboo[4] = {};
    for (int m = 0; m < n; m++) {
      int ix = (i & (3U << (m * 2))) >> (m * 2);
      if (ix != 0) {
        bamboo[ix] += l[m];
        mp += 10;
      }
    }
    if (bamboo[1] == 0 || bamboo[2] == 0 || bamboo[3] == 0) continue;
    mp += bamboo[1] > a ? bamboo[1] - a : a - bamboo[1];
    mp += bamboo[2] > b ? bamboo[2] - b : b - bamboo[2];
    mp += bamboo[3] > c ? bamboo[3] - c : c - bamboo[3];
    mp -= 30;
    if (ans > mp) ans = mp;
  }
  printf("%d\n", ans);
}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int> > vpii;
typedef vector<pair<ll, ll> > vpll;

#define pll pair<ll,ll>
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define rep(i,n) for (int i = 0; i < n; ++i) 
#define REP(i,k,n) for (int i = k; i <= n; ++i) 
#define REPR(i,k,n) for (int i = k; i >= n; --i)
#define INF (int)1e9
#define pb push_back
#define watch(x) cout << (#x) << " is " << (x) << endl
#define sz(a) int((a).size())
#define endl '\n' // remove for interactive

const ll mod = 1e9 + 7;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

const int N = 2e5 + 10;
int ans[N];

void solve()
{
    int n; cin>>n;
    rep(i, n-1)
    {
        int x; cin>>x;
        ans[x]++;
    }
    REP(i, 1, n)
    {
        cout<<ans[i]<<endl;
    }
}

int main()
{
    // clock_t start, end;
    // start = clock();
    ios_base::sync_with_stdio(0); //cant use scanf, printf
    cin.tie(0);cout.tie(0); // no longer auto flush cout before each cin, remove for interactive
    int t = 1;
    // cin>>t;
    REP(i, 1, t)
    {
        solve();
        
    }
    // end = clock();
    // double time_taken = double(end - start) / double(CLOCKS_PER_SEC); 
    // watch(time_taken);
    return 0;
    
}



/*before sub
TEST: 0, 1, equal, -ve, bounds(random and ez)
ERR/WA: loop vars, out of bounds, endl, finish taking inputs, large doubles, larger INF, corr mod, t
RE: double dec, integer overflow(ll or 1LL mult)
*/





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

using namespace std;

#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define SORT(v) sort(v.begin(), v.end())
typedef long long ll;

int main()
{
    int n;
    ll ans = 1;
    string s;
    cin >> n >> s;
    vector<int> a(3);
    REP(i, 3)
    a.at(i) = 0;
    REP(i, n)
    {
        if (s.at(i) == 'R')
            a.at(0)++;
        if (s.at(i) == 'G')
            a.at(1)++;
        if (s.at(i) == 'B')
            a.at(2)++;
    }
    REP(i, 3)
    ans *= (ll)a.at(i);
    for (int j = 1; j < n - 1; j++)
    {
        REP(i, j)
        {
            if ((s.at(i) != s.at(j)) && (j < 2 * j - i) && (2 * j - i < n) && s.at(2 * j - i) != s.at(i) && s.at(2 * j - i) != s.at(j))
                ans--;
        }
    }

    cout << ans;
}

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

int main() {
    string s;
    cin >> s;
    string ans;
    if (s[s.size() - 1] == 's') {
        ans = s + "es";
    }
    else ans = s + "s";
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3600
n, k = map(int, input().split())
s = input()

l_01 = []
l_10 = []
if s[0] == '1':
    l_01.append(0)
for i in range(n-1):
    if s[i] == '0' and s[i+1] == '1':
        l_01.append(i+1)
    elif s[i] == '1' and s[i+1] == '0':
        l_10.append(i+1)
if s[-1] == '1':
    l_10.append(n)

cnt_0 = len(l_01) - 1
if s[0] == '0':
    cnt_0 += 1
if s[-1] == '0':
    cnt_0 += 1
cnt_1 = len(l_01)

if k >= cnt_0:
    print(n)
else:
    res = 0
    i = 0
    while i + k < cnt_1:
        res = max(res, l_10[i+k] - l_01[i])
        i += 1
    if s[0] == '0':
        res = max(res, l_10[k-1])
    if s[-1] == '0':
        res = max(res, n - l_01[-k])
    print(res)

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

int main() {
  int n;
  cin >> n;
  vector<int> a(n+1);
  vector<int> b(n+1);
  rep(i,n) cin >> a[i+1];

  for(int i = n; i >= 1; --i){
    int s = a[i];
    for(int j = n / i; j >= 1; --j){
      if(j != 1) s -= b[i * j];
      if(j == 1) b[i] = abs(s) % 2;
    }
  }

  int ans = 0;
  rep(i,n) ans += b[i+1];
  cout << ans << endl;
  for(int i = 1; i <= n ; ++i) {
    if(b[i]==1) cout << i << " ";
  }
  return 0;
}

Measured memory_bytes: 2432
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
using namespace std;
#define MOD 1000000007
#define EPS 10e-8

int main(){
    int n,sa;
    int R[2000001];
    cin >> n;
    rep(i,n){
        cin >> R[i];
    }
    int mi = R[0];
    sa=R[1]-R[0];
    for(int i=1;i<n;i++){
        if(R[i]-mi>sa){
            sa=R[i]-mi;
        }
        if(mi > R[i]){
            mi = R[i];
        }
    }
    cout << sa << endl;
}


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

int main(){
    string S;
    cin >> S;
    if(S=="SAT"){
        cout << "1" << endl;
    }else if(S=="FRI"){
        cout << "2" << endl;
    }else if(S=="THU"){
        cout << "3" << endl;
    }else if(S=="WED"){
        cout << "4" << endl;
    }else if(S=="TUE"){
        cout << "5" << endl;
    }else if(S=="MON"){
        cout << "6" << endl;
    }else{
        cout << "7" << endl;
    }
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        List<Integer> x = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            x.add(sc.nextInt());
        }
        sc.close();

        Collections.sort(x);

        int diff = m - n;
        if (diff <= 0) {
            System.out.println(0);
        } else {
            List<Integer> diffList = new ArrayList<>();
            for (int i = 1; i < m; i++) {
                diffList.add(x.get(i) - x.get(i - 1));
            }
            Collections.sort(diffList);

            int ans = 0;
            for (int i = 0; i < diff; i++) {
                ans += diffList.get(i);
            }
            System.out.println(ans);
        }

    }

}


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

int main()
{
	int a,b;
	cin>>a>>b;
	if(a>=13) cout<<b;
	else if(a>=6&&a<=12) 
	{
		cout<<b/2;
		if(b%2!=0) cout<<".5";
	}
	else cout<<0;
	return 0;
}

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

using namespace std;

#define rep(i, x)   for (__typeof(x) i = 0; i < x; i++)
#define mp             make_pair
#define pb             push_back
#define fi             first
#define se             second
#define sz(x)          (int)((x).size())
#define all(x)         (x).begin(), (x).end()
#define sci(x)         int x;       scanf("%d", &x);
#define scii(x, y)     int x, y;    scanf("%d %d", &x, &y);
#define sciii(x, y, z) int x, y, z; scanf("%d %d %d", &x, &y, &z);
#define TC(x)          sci(x); while(x --)
#define eprintf(...)   fprintf(stderr, __VA_ARGS__)
#define debug(x)       { cerr << #x << " = " << x << endl; }
#define repi(i, x)  for (__typeof(x) i = x-1; i >= 0; i --)
#define fore(itr, x)   for (__typeof(x.begin()) itr = x.begin(); itr != x.end(); itr ++)
#define forei(itr, x)  for (__typeof(x.end()) itr = x.end() - 1; itr != x.begin() - 1; itr --)
typedef long long      ll;
typedef pair<int, int> ii;
typedef pair<ii, int>  iii;
typedef vector<int>    vi;
typedef vector<ii>     vii;
typedef vector<iii>    viii;
typedef vector<vector<int> > vvi;
const   int            infi = numeric_limits<int>::max();
const   double         eps = 0;
const   int            ms  = 0;

int main()
{
    ios::sync_with_stdio(false);//endl->"\n"
    cin.tie(0);
    int N;
    cin >> N;
    vi l(N);
    rep(i, N)cin >> l[i];
    sort(all(l));
    int s = 0;

    rep(i, N-1)s+=l[i];
    if(s > l[N-1])cout << "Yes" << "\n";
    else cout << "No" << "\n";
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.second != b.second){
        return a.second > b.second;
        
    }else{
        return a.first < b.first;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll N,H;
    cin >>N>>H;
    vector<Pi>ab(N);
    rep(i,N){
        ll a,b;
        cin>>a>>b;
        ab[i]=mp(a,b);
    }

    sort(all(ab));
    ll ma=ab[N-1].first;
    ll mb=ab[N-1].second;
    ab[N-1].second=-1;
    sort(all(ab),compare);
    ll ans=0;
    rep(i,N){
        if(H<=mb){
            ans++;
            cout<<ans<<endl;
            return 0;
        }else if(ab[i].second>ma){
            H-=ab[i].second;
            ans++;
            if(H<=0){
                cout<<ans<<endl;
                return 0;
            }
        }else{
            break;
        }
    }
    ans++;
    H-=mb;
    if(H<=0){
        cout<<ans<<endl;
        return 0;
    }
    ans+=(H-1)/ma + 1;

    cout << ans << endl;


    return 0;
    

}

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

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

    VI w(n), e(n);
    w[0] = 0;
    e[n-1] = 0;
    rep(i,n-1){
        if(s[i]=='W'){
            w[i+1] = w[i] + 1;
        }else{
            w[i+1] = w[i];
        }
        if(s[n-1-i]=='E'){
            e[n-2-i] = e[n-1-i] + 1;
        }else{
            e[n-2-i] = e[n-1-i];
        }
    }

    int ans = n;
    rep(i,n){
        ans = min(ans, w[i]+e[i]);
    }

    cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3076
import sys
state_size = 50
#generate states
init = [0] + [state_size - 1] * (state_size - 1)
states = [init]
for i in xrange(1,state_size):
    topush = []
    for j in xrange(state_size):
        if i-1 == j:
            topush.append(states[-1][j] + state_size)
        else:
            topush.append(states[-1][j] - 1)
    states.append(topush)

K = int(sys.stdin.readline())

P = K/state_size
Q = K%state_size

ret = states[Q]
ret = [x+P for x in ret]

print state_size
print ' '.join(map(str,ret))


Measured memory_bytes: 2692
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#ifdef DEBUG
#define display(x) cerr << #x << " = " << x << endl;
#define displaya(a, st, n)\
	{cerr << #a << " = {";\
	for(int qwq = (st); qwq <= (n); ++qwq) {\
		if(qwq == (st)) cerr << a[qwq];\
		else cerr << ", " << a[qwq];\
	} cerr << "}" << endl;}
#define displayv(v) displaya(v, 0, (int)(v).size() - 1)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define display(x) ;
#define displaya(a, st, n) ;
#define displayv(v) ;
#define eprintf(...) if(0) fprintf(stderr, "...")
#endif
template<typename T> bool chmin(T &a, const T &b) { return a > b ? a = b, true : false; }
template<typename T> bool chmax(T &a, const T &b) { return a < b ? a = b, true : false; }

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
#endif
	string s;
	cin >> s;
	vector<int> f(s.size()), g(s.size());
	int n = s.size();
	f[0] = 1;
	g[0] = 0;
	if(n >= 2) g[1] = 1;
	if(n >= 2) if(s[0] == s[1]) f[1] = 0; else f[1] = 2; else;
	for(int i = 2; i < n; ++i) {
		g[i] = f[i - 2] + 1;
		if(s[i] != s[i - 1]) f[i] = f[i - 1] + 1;
		chmax(f[i], g[i - 1] + 1);
	}
	displayv(f);
	displayv(g);
	cout << max(f.back(), g.back()) << endl;
	return 0;
}


Measured memory_bytes: 2196
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=32e4;

int a[N];
int main(){
	int n,k;
	cin>>k>>n>>a[0];
	int mx=0;
	for(int i=1;i<n;i++){
		cin>>a[i];
		mx=max(mx,a[i]-a[i-1]);
	}
	cout<<k-max(mx,a[0]+k-a[n-1]);
	
	return 0;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <iostream>
#include <vector>
#include <iostream>
#include <cstdio>
#include <complex>
#include <utility>
#define X real()
#define Y imag()
#define EPS (1e-10)
using namespace std;
typedef complex<double> P;
typedef pair<P,P> L;
typedef vector<P> Poly;
namespace std{
  bool operator<(const P& a, const P& b){
    return a.X != b.X ? a.X < b.X : a.Y < b.Y;
  }
}

double cross(P a, P b){
  return a.X*b.Y - a.Y*b.X;
}

bool solve(Poly p){
  int n = p.size();
  for(int i = 0; i < n/2; ++i){
    if(abs(cross(p[i+1]-p[i], p[(n/2+1+i)%n]-p[(n/2+i)%n])) > EPS ||
       abs(norm(p[i+1]-p[i]) - norm(p[(n/2+1+i)%n]-p[(n/2+i)%n])) > EPS){
      return false;
    }
  }
  return true;
}

int main(){
  int N;
  cin >> N;
  double x, y;
  Poly p;
  for(int i = 0; i < N; ++i){
    cin >> x >> y;
    p.push_back(P(x,y));
  }
  if(N%2){
    cout << "NA" << endl;
    return 0;
  }
  P m = (p[0]+p[N/2])/2.0;
  if(solve(p)) printf("%.10lf %.10lf\n", m.X, m.Y);
  else cout << "NA" << endl;
  return 0;
}

Measured memory_bytes: 3272
import scala.io.StdIn.readLine

object Main {

  def main(args: Array[String]) = {
    var n = readLine.split(" ").map(_.toInt)

    while( n(0) != 0 || n(1) != 0) {
      val str1 = "#."*n(1)
      val str2 = ".#"*n(1)

      for(i <- 0 to n(0)-1) {
        if(i%2==0)
          println(str1.take(n(1)))
        else
          println(str2.take(n(1)))
      }
      println()
      n = readLine.split(" ").map(_.toInt)
    }
  }
}

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

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

	int w = 0;
	int l = 0;
	for(int i = 0; i < s.size(); i++){
		if(s[i] == 'o') w++;
		else l++;
	}

	if(15 - s.size() + w >= 8) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,a,b) for(int i =(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define REPS(i,n) for(int i=1;i<=(n);i++)
#define RREPS(i,n) for(int i=(n);i>0;i--)
#define mp make_pair
#define pb(a) push_back(a)
typedef long long ll;
#define MAX_N 200001
vector<int> G[MAX_N];
bool flag[MAX_N];

int main(){
    int N,M;
    scanf("%d %d",&N,&M);
    REP(i,M){
        int a,b;
        scanf("%d %d",&a,&b);
        G[a].pb(b);
        G[b].pb(a);
    }
    flag[1] = true;
    queue<pair<int,int> > que;
    que.push(mp(1,0));
    bool ans = false;
    while(! que.empty()){
        pair<int,int> qd = que.front();
        que.pop();
        if(qd.second == 3) break;
        if(qd.first == N){
            ans = true;
            break;
        }
        int v = qd.first;
        int d = qd.second;
        REP(i,G[v].size()){
            if(! flag[G[v][i]]){
                flag[G[v][i]] = true;
                que.push(mp(G[v][i],d+1));
            }
        }
    }
    if(ans) printf("POSSIBLE\n");
    else printf("IMPOSSIBLE\n");
    return 0;
}


Measured memory_bytes: 13040
#include <iostream>
#include<time.h>
#include<string>
#include<cstring>
#include <cstdio>
#include<utility>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<bitset>
#include<queue>
#include<stack>
#include<set>
#include <limits>
#include <climits>
#include <numeric>
#include<cassert>
#include<cctype>
#include<iterator>
#include<unordered_map>
#include <cassert>
#include <bit>
#include <cstdint>
using namespace std;
typedef long long ll;
typedef unsigned long long LL;
typedef vector<ll>VI;
typedef vector<bool>VB;
typedef pair<ll,ll>P;
typedef pair<double,double>P_D;
#define VV(T) vector<vector<T>>
#define PI 3.1415926535897932384626433832795
#define rep(i, n) for (ll i = 0; i < (ll)n; i++)
#define reprev(i, n) for (ll i = (ll)n - 1; i >= 0; i--)
#define bitrep(bit,A) for(int bit=A; ;bit=(bit-1)&A)
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) (ll)((a).size())
#define c_max(a, b) (((ll)a)>((ll)b)?(a):(b))
#define c_min(a,b) (((ll)a)<((ll)b)?(a):(b))
#define chmax(x,a) x=c_max(x,a)
#define chmin(x,a) x=c_min(x,a)
#define vmax(v) *max_element(ALL(v))
#define vmin(v) *min_element(ALL(v))
#define SORT(c) stable_sort(ALL(c))
#define $(x) {cout<<#x<<" = " <<(x)<<endl;}
#define fi first
#define se second
#define MAX 100100//5
#define MAX2 200100
#define MAX_6 1001001//6
#define MAX_7 10010010//7
#define SENTINEL 2000000000//9
#define NIL -1
const int MOD = 1000000007;
#define INF 1<<30
#define INFTY 1LL<<61
#define MAX_INT INT_MAX
#define Endl '\n'
#define greater greater<int>()
inline ll GCD(ll a,ll b){return b?GCD(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/GCD(a,b);}
using Edge=pair<int,ll>;
using Graph=vector<vector<ll> >;//ll or Edge
using Edge=pair<int,ll>;
//const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
// g++ -o a a.cpp -Wall -lm -std=c++17
ll n,a[MAX2];
ll cnt[MAX_6];
bool ok[MAX_6];
int main(){
    cin>>n;
    rep(i,n)cin>>a[i];
    rep(i,n)cnt[a[i]]++;
    rep(i,MAX_6)ok[i]=true;
    for(int i=1;i<MAX_6;i++){
        if(0<cnt[i]){
            if(2<=cnt[i])ok[i]=false;
            for(int j=2*i;j<MAX_6;j+=i)ok[j]=false;
        }
    }
    int ans=0;
    rep(i,n)if(ok[a[i]] && cnt[a[i]])ans++;
    cout<<ans<<endl;
}

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

    using namespace std;

    #define MP make_pair
    #define ALL(x) (x).begin(),(x).end()
    #define SZ(x) (int((x.size())))
    #define fi first
    #define se second
    #define REP(i, a, n) for (int (i)=(a);(i)<(n);(i)++)
    #define PER(i, a, n) for (int (i)=(n)-1;(i)>=(a);(i)--)

    typedef long double ld;
    typedef long long ll;
    typedef vector<int> VI;
    typedef pair<int, int> PII;
    typedef pair<ll, ll> PLL;
    typedef vector<ll> VL;
    typedef vector<PLL> VPL;
    typedef vector<PII> VPI;

    //#ifndef ONLINE_JUDGE
    #define dbb(x)        { cerr << #x << " = " << x << "\t";      }
    #define db(x)        { dbb(x); cerr << endl; }
    #define db2(x, y)    { dbb(x); dbb(y); cerr << endl; }
    #define db3(x, y, z)    { dbb(x); dbb(y); dbb(z); cerr << endl; }
    //#else
    //#define dbb(x)		;
    //#define db(x)		;
    //#define db2(x,y)	;
    //#define db3(x,y,z)	;
    //#endif



    const ll MOD = 1000000007ll;

    ll powmod(ll a, ll b) {
        ll res = 1;
        a %= MOD;
        assert(b >= 0);
        for (; b; b >>= 1) {
            if (b & 1) res = res * a % MOD;
            a = a * a % MOD;
        }
        return res;
    }

    template<typename t1, typename t2>
    inline bool upmax(t1 &a, t2 b) {
        if (a < (t1) b) {
            a = (t1) b;
            return true;
        } else return false;
    }

    template<typename t1, typename t2>
    inline bool upmin(t1 &a, t2 b) {
        if (a > (t1) b) {
            a = (t1) b;
            return true;
        } else return false;
    }

    template<typename T>
    inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

    template<typename T>
    inline T lcm(T a, T b) { return a * (b / gcd(a, b)); }

    template<typename T>
    inline T sqr(T a) { return a * a; }

    int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
    int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
    int dkx[] = {-1, -1, 1, 1, -2, -2, 2, 2};
    int dky[] = {-2, 2, -2, 2, -1, 1, -1, 1};

    const int INF = 1000000404;
    const ll LINF = 1e18 * (1ll);
    const ld PI = 3.14159265358979323846;
    const ld EPS = 1e-9;

    int SQ = 318;
    int timer = 0;

    #define N 1010


    void solve() {

        string s;
        cin >> s;


        int n = SZ(s);
        ll foo = 0;
        ll ans = 0;

        for (int i = 0; i < n - 1; i++) {
    
            if (s[i] == 'A') {
                foo++;
            }
            else if (s[i] == 'B' && s[i + 1] == 'C') {
                ans += foo;
                i++;
            } else foo = 0;
        }
        cout << ans << endl;


    }

    int main() {

    #ifdef HOME
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #else
        //freopen("input.in", "r", stdin);
        //freopen("output.out", "w", stdout);
    #endif

        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);

        int t = 1;
        //cin >> t;

        while (t--) {

            solve();

        }

        return 0;
    }


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

using namespace std;
//next 保留字 
int u[400005];
int v[400005];
int w[400005];
int nextt[400005];
int head[100005];
int dis[100005];
bool vis[100005];
int cnt=0;
int f;
void add(int u1,int v1,int w1)
{
	cnt++;
	u[cnt]=u1;
	v[cnt]=v1;
	w[cnt]=w1;
	nextt[cnt]=head[u1];
	head[u1]=cnt;
}
void find(int x)
{
	int j=head[x];
	while(j!=-1)
	{
		if(!vis[v[j]])
		{
			vis[v[j]]=true;
			dis[v[j]]=dis[x]+w[j];
			find(v[j]);
		}
		else
		{
			if(dis[v[j]]!=dis[x]+w[j])
			{
				f=0;
				return;
			}
		}
		j=nextt[j];
	}
}
int main()
{
	memset(dis,0,sizeof(dis));
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=2*n;i++) head[i]=-1;
	for(int i=1;i<=m;i++)
	{
		int l,r,d;
		cin>>l>>r>>d;
		add(l,r,-d);
		add(r,l,d);
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			f=1;
			vis[i]=true;
			find(i);
			if(f==0||dis[i]!=0)
			{
				cout<<"No"<<endl;
				return 0; 
			}
		}
	}
	cout<<"Yes"<<endl;
	return 0;
} 

Measured memory_bytes: 9216
#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
//long long int countt[200003];
#include<ext/pb_ds/assoc_container.hpp> // include the associative containers or group of templates such as set, multimap, map etc.
#include<ext/pb_ds/tree_policy.hpp> // include the tree_order_statistics_node update
using namespace __gnu_pbds; //necessary for the GNU based Policy based data structures.
typedef tree<pair<int,int> ,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define int long long
#define endl "\n"



signed main()
{
    FAST;
    int t;
    t=1;
    
    while(t--)
    {
        int i=0,j=0,k=0,n=0,m=0,count=0,temp=0;
        int temp1=0,temp2=0,temp3=0,x=0,l=0,y=0,sum=0;
        int left=0,up=0,down=0,start=0,end=0,r=0,q=0,total=0;
        int maxx=0,minn=0,curr=0,ans=0,places=0,zeroes=0,low=0,high=0;
        int prev=0,mid=0,z=0,d=0,val=0,pos=0,shift=0,h=0,right=0,var=0;
        
        cin>>x>>n;
        int a[n];
        map<int,int> mp;
        for(i=0;i<n;i++)
        {
            cin>>a[i];
            mp[a[i]]=1;
        }
        
        sort(a,a+n);
        
        temp = x;
        while(1)
        {
            if(mp.count(temp)==0)
            {
                ans = temp;
                temp1 = x - temp;
                break;
            }
            
            temp--;
        }
        
        temp = x;
         while(1)
        {
            if(mp.count(temp)==0)
            {
                if(temp-x<temp1)
                ans = temp;
                
                break;
            }
            
            temp++;
        }
        
        cout<<ans<<endl;
        
        
    }
        
    
    
    
    
}

Measured memory_bytes: 3660
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AtCoder
{
    public class ABC_102_C
    {
        public static int SumDigits(int num)
        {
            int sum = 0;
            while (num != 0)
            {
                sum += num % 10;
                num /= 10;
            }
            return sum;
        }

        public static void Main()
        {
            var str = Console.ReadLine().Split(' ');
            var n = int.Parse(str[0]);
            var a = int.Parse(str[1]);
            var b = int.Parse(str[2]);          
            var result = 0;
          
            for (int i = 1; i <= n; i++)
            {
                var sum = SumDigits(i);
                if (sum >= a && sum <= b)
                {
                    result += i;
                }
            }
            Console.WriteLine(result);
            //Console.Read();
        }
    }
}

Measured memory_bytes: 11092
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		while (true) {
			String str[] = br.readLine().split(" ");
			int n = Integer.parseInt(str[0]);
			int m = Integer.parseInt(str[1]);

			if (n == 0 && m == 0)
				break;

			ArrayList<ArrayList<Schedule>> list = new ArrayList<>();
			for (int i = 0; i < m; i++) {
				list.add(new ArrayList<Schedule>());
			}

			String s = br.readLine();
			int r = Integer.parseInt(s);
			int last[] = new int[n];

			for (int i = 0; i < r; i++) {
				str = br.readLine().split(" ");
				int T = Integer.parseInt(str[0]);
				int N = Integer.parseInt(str[1]) - 1;
				int M = Integer.parseInt(str[2]) - 1;
				int S = Integer.parseInt(str[3]);
				if (S == 1)
					last[N] = T;
				else
					list.get(M).add(new Schedule(last[N], T));
			}
			for (int i = 0; i < m; i++) {
				Collections.sort(list.get(i));
			}

			s = br.readLine();
			int q = Integer.parseInt(s);

			for (int i = 0; i < q; i++) {
				str = br.readLine().split(" ");
				int start = Integer.parseInt(str[0]);
				int end = Integer.parseInt(str[1]);
				int user = Integer.parseInt(str[2]) - 1;

				int ans = 0, la = start;
				for (Schedule sche : list.get(user)) {
					la = Math.max(la, sche.start);
					ans += Math.max(Math.min(sche.end, end) - la, 0);
					la = Math.max(la, sche.end);
				}
				System.out.println(ans);
			}
		}
	}
}

class Schedule implements Comparable<Schedule> {

	int start, end;

	public Schedule(int start, int end) {
		this.start = start;
		this.end = end;
	}

	@Override
	public int compareTo(Schedule s) {
			return this.start - s.start;
	}
}


Measured memory_bytes: 39508
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
string s;
int l;
int main()
{
    cin>>s;
    l=s.size();
    for(register int i=0;i<l;i++)
    {
        if(s[i]=='C')
        {
            for(register int j=i+1;j<l;j++)
            {
                if(s[j]=='F')
                {
                    cout<<"Yes";
                    return 0;
                }
            }
        }
    }
    cout<<"No";
    return 0;
}

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

int hoge(string s, char c){
    int f = 1;
    for(int i = 0; i < s.size(); i++)if(s[i] == c)f = 0;
    if(f)return 2000;
    int res = 0;
    for(;;){
        int f = 1;
        for(int i = 0; i < s.size(); i++)if(s[i] != c)f = 0;
        if(f)break;
        string s2(s.size() - 1, '*');
        for(int i = 0; i < s2.size(); i++){
            if(s[i] == c || s[i + 1] == c)s2[i] = c;
        }
        s = s2;
        res++;
    }
    return res;
}

int main(){
    string s;
    cin >> s;
    int ans = 1919;
    for(char c = 'a'; c <= 'z'; c++){
        ans = min(ans, hoge(s, c));    
    }
    cout << ans << endl;

    return 0;
}


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

string S, T;
map<char, char> m1,m2; // 置換表

int main(){
    cin >> S >> T;
    int size = (int)S.size();
    // S目線、T目線両方から考える。
    REP(i,size){
        if(m1[S[i]]==0){ // この文字の置換は初出
            m1[S[i]] = T[i];
        } else {
            if(m1[S[i]]!=T[i]){ // すでに置換があるのに、今の置換と異なる。
                cout << "No" << endl;
                return 0;
            }
        }
    }

    REP(i,size){
        if(m2[T[i]]==0){ // この文字の置換は初出
            m2[T[i]] = S[i];
        } else {
            if(m2[T[i]]!=S[i]){ // すでに置換があるのに、今の置換と異なる。
                cout << "No" << endl;
                return 0;
            }
        }
    }

    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 776
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std; 
int main(){
int n,k;
cin >>n >>k;
vector<int> p;
for(int i=0; i<n; i++){
    int num;
    cin >>num;
    p.push_back(num);
}
sort(p.begin(),p.end()); //昇順ソート
int sum=0;
for(int i=0; i<k; i++){
    sum+=p[i];
}
cout <<sum <<endl;
return 0;
}

Measured memory_bytes: 3632
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int i,j,n,m1,m2,m3,m4,s1,s2,s3,s4,tim[2000000],order[2000000];

int compt(const void* x,const void* y){
	int xx = *(int*)x;
	int yy = *(int*)y;
	return tim[xx]-tim[yy];
}

int main(){
	while(scanf("%d",&n)*n){
		for(i=0;i<n;i++){
			scanf("%d %d %d %d %d %d %d %d %d",&order[i],&m1,&s1,&m2,&s2,&m3,&s3,&m4,&s4);
			tim[order[i]]=(m1+m2+m3+m4)*60+s1+s2+s3+s4;
		}
		qsort(order,n,sizeof(int),compt);
		printf("%d\n%d\n%d\n",order[0],order[1],order[n-2]);
	}
	return 0;
}

Measured memory_bytes: 2736
=begin
－－－－－－－－－－－－－－
n = スイッチの数
m = 電球の数
k = 電球[i]に繋がっているスイッチ
a = スイッチを表す配列 (N個分)
pi = スイッチの最終状態
t = スイッチの押しパターンごとの電球の状態を記録
ans = 答えの数
－－－－－－－－－－－－－－
1: 各スイッチにどの電球が繋がっているのかを記録する
  1.1: i 番目の電球に繋がっている スイッチ k を受け取り、k をループする
    1.1.1: k 番目のスイッチ(a[k]) が繋がっている 電球[i]を 2進数で記録する (スイッチ k[j] には複数の 電球m[i] が繋がっている可能性のあるため ビットOR で受け取る)
2: スイッチの最終状態 pi を 2 進数で 受け取る
3: スイッチの押しパターンを全て試す
  3.1: パターンごとに 電球の状態 t を記録し、スイッチの最終状態 pi と一致すれば ans += 1
4: ans を出力
=end

n, m = gets.split.map(&:to_i)
a = Array.new(n,0)
pi = 0
ans = 0

for i in 0..(m-1) do
  k = gets.split.map{|v| v.to_i - 1}
  k.shift()
  k.each do |j|
    a[j] |=  1<<i
  end
end

a_pi = gets.split.map(&:to_i)
a_pi.each_with_index do |x, i|
  pi |= x << i
end

s = 0;
while(s < (1<<n)) do
  t = 0;
  for i in 0..(n-1) do
    if s[i] != 0
      t ^= a[i];
    end
  end
  ans += 1 if t == pi
  s += 1
end

puts ans


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

#define ll long long int
#define endl '\n'

void solve()
{
    ll x;
    cin>>x;
    if(x==0)
    	cout<<"1"<<endl;
    else if(x==1)
    	cout<<"0"<<endl;

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    #ifdef JAY
        freopen("C:/Users/jayra/Desktop/cp/input.txt","r",stdin);
        freopen("C:/Users/jayra/Desktop/cp/output.txt","w",stdout);
    #endif

    
        solve();
   
}

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

using namespace std;

//#define FILE_IO

typedef long long LL;

const int mod = 1e9 + 7;

LL K;
int N;
int a[55][55];
int aux[55][55];
int dp[55][55];

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    cin >> N >> K;
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= N; j++)
            cin >> a[i][j];

    for(int i = 1; i <= N; i++)
        dp[i][1] = 1;

    auto clr = [&](int a[55][55])
    {
        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= N; j++)
                a[i][j] = 0;
    };

    auto mul = [&](int a[55][55], int b[55][55], int c[55][55])
    {
        clr(c);
        for(int k = 1; k <= N; k++)
            for(int i = 1; i <= N; i++)
                for(int j = 1; j <= N; j++)
                    c[i][j] = (c[i][j] + (1LL * a[i][k] * b[k][j]) % mod) % mod;
    };

    auto cpy = [&](int a[55][55], int b[55][55])
    {
        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= N; j++)
                b[i][j] = a[i][j];
    };

    for(int bt = 0; (1LL << bt) <= K; bt++)
    {
        if( (K >> bt) & 1 )
        {
            mul(a, dp, aux);
            cpy(aux, dp);
        }

        mul(a, a, aux);
        cpy(aux, a);
    }

    int ans = 0;
    for(int i = 1; i <= N; i++)
        ans = (ans + dp[i][1]) % mod;

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 256
dic={
     "A":1,
     "B":2,
     "C":3,
     "D":4,
     "E":5,
     "F":6,
     "G":7,
     "H":8,
     "I":9,
     "J":10,
     "K":11,
     "L":12,
     "M":13,
     "N":14,
     "O":15,
     "P":16,
     "Q":17,
     "R":18,
     "S":19,
     "T":20,
     "U":21,
     "V":22,
     "W":23,
     "X":24,
     "Y":25,
     "Z":26

}

gyaku={
    1:"A",
    2:"B",
    3:"C",
    4:"D",
    5:"E",
    6:"F",
    7:"G",
    8:"H",
    9:"I",
    10:"J",
    11:"K",
    12:"L",
    13:"M",
    14:"N",
    15:"O",
    16:"P",
    17:"Q",
    18:"R",
    19:"S",
    20:"T",
    21:"U",
    22:"V",
    23:"W",
    24:"X",
    25:"Y",
    26:"Z"
}
N=int(input())
li=list(input())

for i in range(len(li)):
  a=dic[li[i]]+N
  if a>26:
    a-=26
  li[i]=gyaku[a]
for i in range(len(li)):
  print(li[i],end="")


Measured memory_bytes: 4724
#include <iostream>
#include <cstdio>
using namespace std;
int n, L;
long long a[100010];
int ans[100010], top;
int main () {
	scanf ("%d%d", &n, &L);
	for (int i = 1; i <= n; i++) scanf ("%lld", &a[i]);
	for (int i = 1; i < n; i++) {
		if (a[i] + a[i + 1] >= L) {
			printf ("Possible\n");
			for (int j = 1; j < i; j++) printf ("%d\n", j);
			for (int j = n - 1; j > i; j--) printf ("%d\n", j);
			printf ("%d\n", i);
			return 0;
		}
	}
	printf ("Impossible\n");
	return 0;
}

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

a = list()
b = list()

for i in range(n):
    matrixA = list(map(int, input().split()))
    a.append(matrixA)

for j in range(m):
    b.append(int(input()))

for k in range(n):
    c = 0
    for l in range(m):
        c += a[k][l] * b[l]
    print(c)


Measured memory_bytes: 6008
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;

void calc(int start, vector<int> &res, vector<vector<int> > &graph) {
	queue<int> q;
	q.push(start);
	int cnt = 0;
	res[start] = cnt;
	while(!q.empty()) {
		int q_size = q.size();
		for(int loop = 0; loop < q_size; loop++) {
			int now = q.front(); q.pop();
			//cout << now << endl;
			//res[now] = cnt;
			for(int i = 0; i < graph[now].size(); i++) {
				int next = graph[now][i];
				if(res[next]==-1) {
					q.push(next);
					res[next] = cnt+1;
				}
			}
		}
		cnt++;
		//cout << endl;
	}
	/*
	int now_dist = res[now];
	for(int i = 0; i < graph[now].size(); i++) {
		int next = graph[now][i];
		if(res[next]>-1) continue;
		res[next] =
	}
	*/
}

int main() {
	int n,m;
	cin >> n >> m;
	vector<vector<int> > graph(n*3);
	for(int i = 0; i < m; i++) {
		int u,v;
		cin >> u >> v;
		u--;v--;
		graph[u+0].push_back(v+n);
		//graph[v+0].push_back(u+n);
		graph[u+n].push_back(v+n+n);
		//graph[v+n].push_back(u+n+n);
		graph[u+n+n].push_back(v+0);
		//graph[v+n+n].push_back(u+0);
	}
	int s,t;
	cin >> s >> t;
	vector<int> res(n*3,-1);
	//res[s] = 0;
	calc(s-1,res,graph);
	if(res[t-1]%3!=0) cout << -1 << endl;
	else cout << (res[t-1]/3) << endl;
	//cout << (res[t-1]) << endl;
}


Measured memory_bytes: 17792
import math
N = int(input())
X = list(map(int, input().split()))

Xm = sum(X)/N
Xmi = int(Xm)
Xmc = math.ceil(Xm)

Si = list(map(lambda x:(x-Xmi)**2, X))
Sc = list(map(lambda x:(x-Xmc)**2, X))

ans = min([sum(Si),sum(Sc)])
print(ans)

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

int main() {
    int n;
    cin >> n;
    vector<int> A(100);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }

    int pa = 0;
    int pb = 0;
    sort(A.begin(), A.end(), greater<int>());
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            pa += A[i];
        }
        else {
            pb += A[i];
        }
    }

    cout << pa - pb << endl;

    return 0;
}


Measured memory_bytes: 256
#import sys
#input = sys.stdin.readline
def main():
    A, B = map( int, input().split())
    ans = 0
    if B == 1:
        print(0)
        return
    for i in range(30):
        if A*i - (i-1) >= B:
            print(i)
            break
    
if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <set>
#include <cstdlib>
#include <climits>
#include <iostream>
#include <queue>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#define IN(x,s,g) ((x) >= (s) && (x) < (g))
#define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h)))

const int _dx[] = {0,1,0,-1};
const int _dy[] = {-1,0,1,0};

using namespace std;

int main(){
  int w, h;
  while(cin >> w >> h, w + h){
    vector<string> g(h);
    int sx, sy;

    REP(i,h) cin >> g[i];

    REP(i,h) REP(j,w) if(g[i][j] == '&'){
      g[i][j] = '.';
      sx = j; sy = i;
    }

    typedef pair<int, pair<int, int> > data;
    priority_queue<data, vector<data>, greater<data> > q;
    vector<vector<int> > memo(h, vector<int>(w, -1));

    int ans = INT_MAX;

    q.push(make_pair(0, make_pair(sx, sy)));

    while(q.size()){
      const auto d = q.top(); q.pop();
      const int cost = d.first;
      const int x = d.second.first;
      const int y = d.second.second;

      if(ISIN(x, y, w, h) && memo[y][x] != -1) continue;
      if(ISIN(x, y, w, h)) memo[y][x] = cost;

      if(!ISIN(x, y, w, h)){
	ans = min(ans, cost);
      }else{
	const char prev = g[y][x];
	REP(i,4){
	  const int xx = x + _dx[i];
	  const int yy = y + _dy[i];
	  if(!ISIN(xx, yy, w, h) || memo[yy][xx] == -1){
	    const char next = ISIN(xx, yy, w, h) ? g[yy][xx] : '.';
	    const int cc = prev == '.' && next == '#' ? cost + 1 : cost;
	    q.push(make_pair(cc, make_pair(xx, yy)));
	  }
	}
      }
    }

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

Measured memory_bytes: 1532
#include<bits/stdc++.h>
#define maxn 3005
using namespace std;
int arr[maxn][maxn];
long long dp[maxn][maxn][4];
long long get(int i,int j) {
	return max({dp[i][j][0],dp[i][j][1],dp[i][j][2],dp[i][j][3]});
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int r,c,n;
	cin >> r >> c >> n;
	for(int i=1;i<=n;i++) {
		int x,y,v;
		cin >> x >> y >> v;
		arr[x][y] = v;
	}
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++) {
			dp[i][j][0] = max(get(i - 1,j), dp[i][j - 1][0]);
			for(int k=1;k<=3;k++)
				dp[i][j][k] = max({dp[i][j - 1][k],dp[i][j - 1][k - 1] + arr[i][j],get(i - 1,j) + arr[i][j]});
		}
	cout << get(r,c) << endl;
	return 0;
}


Measured memory_bytes: 320524
//
// Created by Mahmoud Rashad on 11/27/19.
//

#include <bits/stdc++.h>


using namespace std;

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

int main() {
#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.out", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0), cout.precision(10), cout << fixed;

    string s, t;
    cin >> s >> t;
    vector<vector<int>> adjList(26, vector<int>());
    for (int i = 0; i < s.size(); ++i) {
        adjList[s[i] - 'a'].push_back(i);
    }

    for (int i = 0; i < t.size(); ++i) {
        if (adjList[t[i] - 'a'].empty()) {
            cout << -1 << '\n';
            return 0;
        }
    }

    int cnt = 0, curIdx = 0;
    for (int i = 0; i < t.size(); ++i) {
        if (lower_bound(adjList[t[i] - 'a'].begin(), adjList[t[i] - 'a'].end(), curIdx) == adjList[t[i] - 'a'].end()) {
            ++cnt;
            curIdx = 0;
        }
        curIdx = adjList[t[i] - 'a'][lower_bound(adjList[t[i] - 'a'].begin(), adjList[t[i] - 'a'].end(), curIdx) - adjList[t[i] - 'a'].begin()] + 1;
        if (curIdx == (int)s.size()) {
            ++cnt;
            curIdx = 0;
        }
    }

    cout << 1LL * cnt * (long long) s.size() + curIdx << '\n';


    return 0;
}

Measured memory_bytes: 1228
#include <iostream>

using namespace std;

int main() {
    int n;
    long A[100000];
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }
//    srand(8);
//    n = rand() % 20;
//    for (int i = 0; i < n; ++i) {
//        A[i] = (rand() + 1) % 1000000001;
//        if (A[i] <= 0) {
//            A[i] = -A[i];
//        }
//        cout << A[i] << " ";
//    }
//    cout << endl;
    int cnt = 1;
    int zouka;
    if (A[1] == A[0]) {
        zouka = 0;
    } else if (A[1] - A[0] > 0) {
        zouka = 1;
    } else {
        zouka = -1;
    }

    for (int i = 1; i < n - 1; ++i) {
        int z;
        if (A[i + 1] == A[i]) {
            z = 0;
        } else if (A[i + 1] - A[i] > 0) {
            z = 1;
        } else {
            z = -1;
        }
        if (zouka != 0 && z != 0 && zouka != z) {
            cnt += 1;
            i += 1;
            if (i > n - 2) {
                break;
            }
            if (A[i + 1] == A[i]) {
                zouka = 0;
            } else if (A[i + 1] - A[i] > 0) {
                zouka = 1;
            } else {
                zouka = -1;
            }
        } else {
            if (z != 0) {
                zouka = z;
            }
        }

    }
    cout << cnt;
    return 0;
}

Measured memory_bytes: 1024
n=int(input())
a=[[int(i) for i in input().split()] for l in range(n)]
nx=0
ny=0
day=0
for x in a:
    tx=abs(x[1]-nx)
    ty=abs(x[2]-ny)
    tday=x[0]-day
    if (tx+ty-tday)%2==0 and tx+ty<=tday:
        nx=x[1]
        ny=x[2]
        day=x[0]
    else:
        print("No")
        break
else:print("Yes")

Measured memory_bytes: 21108
#include "bits/stdc++.h"
using namespace std;

#define input_from_file freopen("input.txt","r",stdin)
#define output_to_file freopen("output.txt" , "w",stdout)
#define fastio ios_base::sync_with_stdio(0)
#define endl '\n'

const int N = 1e5 + 1 ; 
int in[N];
int dp[N];

int main()
{
     #ifdef LOCAL
        input_from_file;
        output_to_file;
    #endif
    fastio;cin.tie(0);cout.tie(0);
    int n ; cin >> n ;
    for(int i = 1 ; i <= n ; ++i)
        cin >> in[i];
    dp[2] = abs(in[1] - in[2]);
    for(int i = 3 ; i <= n ; ++i)
    {
        dp[i] = min(dp[i-1] + abs(in[i] - in[i-1]) , dp[i-2] + abs(in[i] - in[i-2]));
    }
    cout << dp[n];

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define INF 2147483647
#define INF_LL 9223372036854775807
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

int main() {
	int x;
	cin >> x;
	if (x < 1200)cout << "ABC" << endl;
	else cout << "ARC" << endl;
	return 0;
}

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main() {
    int N, M; cin >> N >> M;
    vector<long long> A(N), B(M), C(M);
    for (int i = 0; i < N; ++i) cin >> A[i];
    sort(A.begin(), A.end());
    B.resize(M);
    C.resize(M);
    for (int i = 0; i < M; ++i) cin >> B[i] >> C[i];

    // C をソート (B をまとめて)
    vector<int> id(M);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int i, int j) {
            return C[i] > C[j];});

    // A (小さい順) と C (大きい順) とを比べて大きい方を足していく
    long long sum = 0;
    long long K = 0;
    for (auto i : id) {
        for (int j = 0; j < B[i]; ++j) {
            if (K >= N) break;
            sum += max(A[K++], C[i]);  
        }
    }
    for (int i = K; i < N; ++i) sum += A[i];        
    cout << sum << endl;
}

Measured memory_bytes: 2944
//Radhe Radhe
#include<bits/stdc++.h>
#define godspeed  ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define ll long long
#define ld long double
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define en '\n'
#define rep(i,n)    for(ll i=0; i<n; i++)
#define rep1(i,a,b)    for(ll i=a; i<=b; i++)
#define repVect(i,n)    for(ll i=0; i<sum.size(); i++)
#define fixed cout.setf(ios::fixed);
#define Precise cout.precision(7);
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;

bool sortBysec(const pair<string,ll>&a,const pair<string,ll>&b)
{

    return (a.se>b.se);

}
int main()
{
    godspeed
    ll  t,n,m,x,i,j,k,l;
    string s;
    map<string,ll>v;
    cin>>t;
    while(t--)
    {
        cin>>s;
        v[s]++;
    }
    vector<pair<string,ll>>all;
    ll maxi=0;
    for(auto it:v)
    {
        maxi=max(it.se,maxi);
        all.pb(mp(it.fi,it.se));
    }
    sort(all.begin(),all.end(),sortBysec);
    vector<string>ans;
    for(auto lol:all)
    {
        if(lol.se==maxi)
            ans.pb(lol.fi);
        else break;
    }
    sort(ans.begin(),ans.end());
    for(auto u:ans)
        cout<<u<<en;
    return 0;
}






Measured memory_bytes: 41132
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
using namespace std;
     
int main(void)
{
  int n;
  cin >> n;
  if(n < 1000){
    cout << "ABC";
  }else{
    cout << "ABD";
  }
}


Measured memory_bytes: 256
#include <cstdio>

#include <algorithm>
#include <functional>
#include <vector>

using namespace std;

typedef long long ll;

int main() {
  int n, q;
  ll m;
  scanf("%d%lld%d", &n, &m, &q);
  vector<int> a(q), b(q), c(q), f(n);
  for (int i = 0; i < n; ++i)
    f[i] = i;
  for (int i = 0; i < q; ++i)
    scanf("%d%d%d", &a[i], &b[i], &c[i]);
  function<int(int)> find = [&](int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
  };
  int cnt = n;
  for (int i = 0; i < q; ++i) {
    if (c[i] == 0) {
      int x = find(a[i]), y = find(b[i]);
      if (x != y) {
        if (x > y) swap(x, y);
        f[y] = x;
        --cnt;
      }
    }
  }
  if (cnt == 2) {
    for (int i = 1; i < n; ++i)
      if (find(i) != 0) {
        f[i] = 0;
        break;
      }
    cnt = 1;
  }
  if (n - cnt + cnt * (cnt - 1LL) / 2 < m) {
    puts("No");
    return 0;
  }
  if (m == n - 1) {
    puts(count(c.begin(), c.end(), 1) ? "No" : "Yes");
    return 0;
  }
  for (int i = 0; i < q; ++i)
    if (c[i] && find(a[i]) == find(b[i])) {
      puts("No");
      return 0;
    }
  puts("Yes");
  return 0;
}


Measured memory_bytes: 1792