akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

int main()
{
   int n;
   cin>>n;
   string s;
   cin>>s;
   if(n==1)
   {
       cout<<"1\n";
       return 0;
   }
   else
   {
       char x=s[0];
       int idx=0,temp=0;
       for(int i=1;i<n;i++)
       {
           if(x==s[i])
           {
               s[i]='A';
           }
           else
           {
               x=s[i];
           }
       }
   }
   int c=0;
   for(int i=0;i<n;i++)
   {
       if(s[i]!='A')
       {
           c++;
       }
   }
   cout<<c<<endl;

}

Measured memory_bytes: 512
#include<stdio.h>
int main()
{
  int a,b;
  scanf("%d %d",&a,&b);
  if(a+b>a*b&&a+b>a-b)
    printf("%d",a+b);
  else if(a-b>a*b)
    printf("%d",a-b);
  else
    printf("%d",a*b);
  return 0;
}

Measured memory_bytes: 128
import math
#切り上げceil,切り捨てfloor
a,b=map(int,input().split())
flag=0
for i in range(1,10000):
  if math.floor(i*0.08)==a and math.floor(i*0.1)==b:
    print(i)
    flag=1
    break
if flag==0:
  print(-1)

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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define ALPHABET    (26)
#define INF         INT_MAX
#define MOD         (1000000007LL)
#define EPS         (1e-10)
#define EQ(a, b)    (abs((a)-(b)) < EPS)

using P   = pair<int, int>;
using LL  = long long;

int di[] = {0, -1, 0, 1};
int dj[] = {1, 0, -1, 0};
// }}}

int main() {
    std::ios::sync_with_stdio(false);
    int n;cin >> n;
    int d[200000];
    for(int i=0;i<n;i++){
        cin >> d[i];
    }
    int m;cin >> m;
    int t[200000];
    map<int, int> mmap;
    for(int i=0;i<m;i++){
        cin >> t[i];
        mmap[t[i]] = 0;
    }
    for(int i=0;i<n;i++){
        mmap[d[i]]++;
    }
    for(int i=0;i<m;i++){
        if(mmap[t[i]] == 0){
            cout << "NO" << endl;
            return 0;
        }else{
            mmap[t[i]]--;
        }
    }
    cout << "YES" << endl;
    return 0;
}


Measured memory_bytes: 11136
#include <stdio.h>
typedef long long ll;
ll min(ll x, ll y) {
	return x < y ? x : y;
}
int main() {
	ll a, b, c;
	scanf("%lld%lld%lld", &a, &b, &c);
	if (a % 2 == 0 || b % 2 == 0 || c % 2 == 0) {
		printf("0\n");
	} else {
		printf("%lld\n", min(a * b, min(b * c, c * a)));
	}
	return 0;
}

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

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

string solve(string s)
{
    string a = "AKIHABARA";
    int n = a.length() - s.length();
    if (n < 0)
        return "NO";
    REP(i, pow(2, s.length() + 1))
    {
        string t = "";
        REP(j, s.length() + 1)
        {
            if (((i >> j) & 1) == 1)
                t += 'A';
            if (s.length() > j)
                t += s[j];
        }
        if (t == a)
            return "YES";
    }
    return "NO";
}

int main()
{
    string S;
    cin >> S;
    cout << solve(S) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
long long int max=0,hoge=0,hogera;
int a,b,c,k;
scanf("%d",&a);
scanf("%d",&b);
scanf("%d",&c);
scanf("%d",&k);
hoge = a+b+c;
if(max<a)max = a;
if(max<b)max = b;
if(max<c)max = c;
hoge -= max;
for(hogera=0;hogera<k;hogera++)max *= 2;
printf("%d",(max+hoge));
return 0;
}

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

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

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

Measured memory_bytes: 256
import java.util.Scanner;

class Main{
    public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	int a,b,c,n;
	n =sc.nextInt();
	for(int i=0;i<n;i++){
	    a=sc.nextInt();
	    b=sc.nextInt();
	    c=sc.nextInt();
	    a*=a;b*=b;c*=c;
	    if(a==b+c||b==a+c||c==a+b)System.out.println("YES");
	    else System.out.println("NO");
	}
    }
}

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

typedef long long lint;
typedef long double louble;

template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

namespace ae86
{
	const int bufl = 1<<15;
	
	char buf[bufl],*s=buf,*t=buf;
	
	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}
	
	inline int ty()
	{
		int a=0,b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}
}
using ae86::ty;

int main()
{
	lint a=ty(),b=ty(),c=ty();
	if(a%2==0 || b%2==0 || c%2==0)puts("0");
	else printf("%lld\n",min(min(a*b,a*c),b*c));

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)


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

  int n,k,s;
  cin >> n >> k >> s;
  rep(i,n){
    int etc = s +1e5;
    if(etc>=1e9) etc = s-1e5;
    if(i<k) cout << s << " \n"[i==n-1];
    else cout << etc << " \n"[i==n-1];

  }

  
  return 0;
    

}


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

#define loop(i,a,b) for(ll i=a; i<b; i++)
#define rloop(i,a,b) for(ll i=a; i>b; i--)
#define all(var) var.begin(), var.end()
#define eloop(var) for(auto elem : var)
#define debug(x) cerr<<#x<<" ----> "<<x<<endl;
#define TT ll tt; cin>>tt; while(tt--)
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a, 0, sizeof(a))
#define INF 0x7fffffff
#define LINF 2000000000000000007
#define MOD 1000000007
#define MAX 100005
typedef long long ll;
typedef long double ld;

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

    //TT
    {
        ll h,n;
        cin>>h>>n;

        ld sum = 0;
        loop(i,0,n) {
            ll t;
            cin>>t;
            sum += t;
        }
        if(sum >= h)
            cout<<"Yes\n";
        else
            cout<<"No\n";
        

    }
    return 0;
}

Measured memory_bytes: 256
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

void main() {
    auto abc = readints;
    int a = abc[0], b = abc[1], c = abc[2];

    double s = (a + b + c) / 2;
    double x = sqrt(s * (s - a) * (s - b) * (s - c));
    writeln(cast(int) x);
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<deque>
#include<algorithm>
#define F first
#define S second
#define all(n) n.begin(),n.end()
using namespace std;
typedef pair<int,int> P;
typedef vector<vector<char> > VVC;

class Pox
{
public:
  P p;
  int cost;
  Pox(P p = P(0,0),int cost = 0):p(p),cost(cost){}
};

int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int h,w;

void print(VVC G)
{
  cout << "---print---" << endl;
  for(int i=0;i<G.size();i++)
    {
      for(int j=0;j<G[i].size();j++)
	cout << G[i][j];
      cout << endl;

    }
  cout << endl;

}

void draw(VVC& G,P p)
{

  for(int i=0;i<4;i++)
    {
      int nx = p.F + dx[i];
      int ny = p.S + dy[i];
      if(!(1<=ny&&ny<=h && 1<=nx&&nx<=w))
	continue;
      if(G[ny][nx] == '&' || G[ny][nx] == '#')
	continue;
      G[ny][nx] = '&';
      draw(G,P(nx,ny));
    }
  
}

int main()
{
  
  while(cin >> w >> h,(w||h))
    {
    
      VVC G;
      P ed;
      G.resize(h+2);
      deque<Pox> deq;
      int mincost[h+3][w+3];
      for(int i=0;i<=h+1;i++)
	{
	  G[i].resize(w+2);
	  string line;
	  if(i == 0 || i == h+1)
	    line = string(h+2,'.');
	  else
	   cin >> line;
	   
	   
	  //cout << "line = " << line << endl;
	  for(int j=0;j<=w+1;j++)
	    {
	      mincost[i][j] = (1<<28);
	      if(i == 0 || j == 0 || i == h+1 || j == w+1)
		{
		  G[i][j] = '.';
		  deq.push_back(Pox(P(j,i),0));
		  mincost[i][j] = 0;
	 	  continue;
		}
	      G[i][j] = line[j-1];
	      if(G[i][j] == '&')
		ed = P(j,i);
	    }
	}
	  
      //print(G);
      draw(G,ed);
      //print(G);     

      int men = (1<<28);
      while(!deq.empty())
	{
	  Pox pox = deq.front(); deq.pop_front();
	  P p = pox.p;
	  int cost = pox.cost;
	  //cout << "p = " << p.F << "," << p.S << " " << cost << endl;
	  if(G[p.S][p.F] == '&')
	    {
	      men = min(men,cost);
	      break;
	    }

	  for(int i=0;i<4;i++)
	    {
	      int nx = p.F + dx[i];
	      int ny = p.S + dy[i];

	      if(!(1<=nx&&nx<=w && 1<=ny&&ny<=h))
		{
		  //cout <<"CONTINUE " << i << " th" << endl;
		  continue;
	      
		}
	      int d = 0;
	      if(G[ny][nx] == '#')
		{
		  //cout << "# IN!" << endl;
		  while(1<=nx&&nx<=w && 1<=ny&&ny<=h && G[ny][nx] == '#')
		    {
		      nx += dx[i];
		      ny += dy[i];
		    }
		  d = 1;
		}
	      
	      //int d = G[ny][nx] == '#'?1:0;
	      if(mincost[ny][nx] > cost + d)
		{
		  // cout << "RENEW = " << cost +d << endl;
		  mincost[ny][nx] = cost + d;
		  if(G[ny][nx] == '&')
		    {
		      men = min(men,mincost[ny][nx]);
		      continue;
		    }
		  deq.push_back(Pox(P(nx,ny),mincost[ny][nx]));
		}
	    }

	}
      cout << men << endl;

    }
  return 0;
}

Measured memory_bytes: 1528
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii> VP;
typedef vector<string> VS;
typedef priority_queue<int> PQ;
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; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
#define mo 1000000007
//priority_queue<int,vector<int>, greater<int> > q2;

ll comb(ll N_, ll C_) {
	const int NUM_ = 400001;
	static ll fact[400002], factr[400002], inv[400002];
	if (fact[0] == 0) {
		inv[1] = fact[0] = factr[0] = 1;
		for (int i = 2; i <= NUM_; ++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i = 1; i <= NUM_; ++i) fact[i] = fact[i - 1] * i%mo, factr[i] = factr[i - 1] * inv[i] % mo;
	}
	if (C_<0 || C_>N_) return 0;
	return factr[C_] * fact[N_] % mo*factr[N_ - C_] % mo;
}
ll modpow(ll a, ll n = mo - 2) {
	ll r = 1;
	while (n) r = r * ((n % 2) ? a : 1) % mo, a = a * a%mo, n >>= 1;
	return r;
}

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

	int N, K; cin >> N >> K;
	int ans = 0;
	int tmp = N;
	int ttmp = 0;
	int tttmp = 0;
	int cnt = 0;
	REP(i, K) {
		cnt += tmp;
		ttmp += tttmp;
		tttmp++;
		tmp--;
	}

	eFOR(i, K, N + 1) {
		//cout << cnt << " " << ttmp << endl;
		ans += cnt - ttmp + 1;
		cnt += tmp;
		ttmp += tttmp;
		tmp--;
		tttmp++;
		ans %= mod;
	}

	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 3652
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int n3 = 3 * n;
		String[] sa = br.readLine().split(" ");
		int[] a = new int[n3];
		for (int i = 0; i < n3; i++) {
			a[i] = Integer.parseInt(sa[i]);
		}
		br.close();

		Arrays.parallelSort(a);

		long ans = 0;
		for (int i = n3 - 2; i >= n; i-=2) {
			ans += a[i];
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 63100
using System;

class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        int[] s = new int[N];
        int sums = 0;
        for (int i = 0; i < N; i++)
        {
            s[i] = int.Parse(Console.ReadLine());
            sums += s[i];
        }

        Array.Sort(s);

        if (sums % 10 == 0)
        {
            for (int i = 0; i < N; i++)
            {
                if (s[i] % 10 != 0)
                {
                    sums -= s[i];
                    break;
                }
                if (i == N - 1) sums = 0;
            }
        }

        Console.WriteLine(sums);
    }
}

Measured memory_bytes: 13652
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

#define REP(i,n) for (int i=0;i<(n);++i)
#define REP2(i,n) for (int i=0;i<=(n);++i)


int main() {

	int N;
	cin >> N;

	if (N < 1000) {
		cout << "ABC" << endl;
	}
	else {
		cout << "ABD" << endl;
	}

	int end;
	cin >> end;

	return 0;
}

Measured memory_bytes: 256
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from collections import deque

    h, w, k = map(int, readline().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, readline().split())
    dict = [[-1] * w for _ in range(h)]
    move = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    for i in range(h):
        c = readline().rstrip().decode()
        for j, cc in enumerate(c):
            if cc == '@':
                dict[i][j] = 0
    q = deque()
    q.append((x1, y1))
    dict[x1][y1] = 0
    while q:
        x, y = q.popleft()
        if x == x2 and y == y2:
            exit(print(dict[x][y]))
        for dx, dy in move:
            for i in range(1, k + 1):
                xx = x + dx * i
                yy = y + dy * i
                if 0 > xx or xx >= h or 0 > yy or yy >= w:
                    break
                if 0 <= dict[xx][yy] <= dict[x][y]:
                    break
                if dict[xx][yy] == -1:
                    q.append((xx, yy))
                dict[xx][yy] = dict[x][y] + 1
    print(-1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 36524
// https://atcoder.jp/contests/abc153/tasks/abc153_e
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define DIV(a, b) ((a - 1) / b + 1)
const int INF = 1e10;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int H, N;
    cin >> H >> N;
    vector<pair<int, int>> v(N);
    REP(i, N) {
        int a, b;
        cin >> a >> b;
        v[i] = {a, b};
    }
    // sort(ALL(v), [](const pair<int, int> &a, const pair<int, int> &b) {
    //     return a.first * b.second > b.first * a.second;
    // });
    vector<int> dp(2e4, INF);
    dp[0] = 0;
    for (auto &x : v) {
        REP(i, H) {
            if (dp[i] != INF && i + x.first < 2e4) {
                dp[i + x.first] = min(dp[i + x.first], dp[i] + x.second);
            }
        }
    }
    int minv = INF;
    FOR(i, H, 2e4) { minv = min(minv, dp[i]); }
    cout << minv << endl;

    return 0;
}

Measured memory_bytes: 384
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma,tune=native")
#include<bits/stdc++.h>
#define rall(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
#define pb push_back
#include <x86intrin.h>
#define pb push_back
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<ll>;
using vpi = vector<pi>;
using ld = long double;
const int maxn = 1e5 + 55, mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int cur = 1, a, b;
	cin >> a >> b;
	int ans = 0;
	while(cur < b) cur += a-1, ans++;
	cout << ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/format.hpp>
#include <boost/range/irange.hpp>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;

bool can_make(string pin, string str) {
  int c = 0;
  for (char ch : str) {
    if (ch == pin.at(c)) ++c;
    if (c == 3) return true;
  }

  return false;
}

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

  int ans = 0;
  rep(pin, 1000) {
    string p = (boost::format("%1$03d") % pin).str();
    if (can_make(p, S)) ++ans;
  }

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


Measured memory_bytes: 384
import sys
n = int(input())
h = list(map(int,input().split()))
inf = float("inf")
dp = [inf]*(n+1)
if n == 2:
    print(abs(h[1]-h[0]))
    sys.exit()

dp[1] = abs(h[1]-h[0])
dp[2] = min(abs(h[2]-h[1])+dp[1], abs(h[2]-h[0]))

for i in range(3,n):
    dp[i] = min(abs(h[i]-h[i-1])+dp[i-1], abs(h[i]-h[i-2])+dp[i-2])
print(dp[n-1])    

Measured memory_bytes: 13928
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

set<int> used;
bool reach(vector<vector<bool>>& V, int i, int j) {
    if (V[i][j]) {return true;}
    if (used.size() == V.size()) {return false;}
    used.insert(i);
    for (int k = 0; k < V.size(); k++) {
        if (i != k && used.count(k) == 0&& V[i][k]) {
            bool result = reach(V, k, j);
            if (result) {
                used.erase(i);
                return true;
            }
        }
    }
    used.erase(i);
    return false;
}

int main() {
    int N, M; cin >> N >> M;
    vector<vector<bool>> V(N, vector<bool>(N));
    rep(i,M) {
        int a, b;
        cin >> a >> b;
        a--,b--;
        V[a][b] = true;
        V[b][a] = true;
    }

    int bridge = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            if (!V[i][j]) continue;
            V[i][j] = false;
            V[j][i] = false;
            bool result = reach(V, i, j);
            V[i][j] = true;
            V[j][i] = true;
            if (!result) bridge++;
        }
    }
    cout << bridge << endl;
}


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

typedef long long ll;
typedef long double Double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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

const string YES = "Yes";
const string NO = "No";

void solve(long long H, long long N, std::vector<long long> A) {
    long long S = accumulate(A.begin(), A.end(), 0ll);
    if( S >= H ){
        cout << YES << endl;
    }else{
        cout << NO << endl;
    }
}

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


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define ll long long
#define mp make_pair
#define pb push_back
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define N 100010
#define Pa 99991
#define Ma 1000000007

int main()
{
    ll h,w;
    cin>>h>>w;
    ll i,j;
    char a[h][w];
    for(i=0;i<h;i++)
    {
        for(j=0;j<w;j++)
        {
            cin>>a[i][j];
        }
    }
    ll dp[h][w];
    memset(dp,0,sizeof(dp));
    for(i=0;i<w;i++)
    {
        if(a[0][i]!='#')
        dp[0][i]=1;
        else
        break;
    }
    for(i=0;i<h;i++)
    {
        if(a[i][0]!='#')
        dp[i][0]=1;
        else
        break;
    }
    for(i=1;i<h;i++)
    {
        for(j=1;j<w;j++)
        {
            if(a[i][j]=='#')
            continue;
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%Ma;
        }
    }
    cout<<dp[h-1][w-1];
        
    return 0;
}

Measured memory_bytes: 9088
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<cstdio>
#include<cmath>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<string>
#include<tuple>
#include<utility>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define rep(i, a, n)  for(int i=a; i<n; i++)
#define REP(i, n)  for(int i=0; i<(int)(n); i++)
#define REPS(i, n)  for(int i=1; i<=(int)(n); i++)
#define PER(i, n) for(int i=(int)(n)-1; i>= 0; i--)
#define PERS(i, n)  for(int i=(int)(n)-1; i>0; i--)
#define FOR(i, c) for(__typeof((c).begin()) i = (c).begin(); i!=(c).end(); i++)
#define RFOR(i, c)  for(__typeof((c).rbegin()) i=(c).rbegin(); i!=(c).end(); i++)
#define ALL(container)  (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) (container).size()
#define FILL0(n)  setfill('0') << right << setw(n)
#define mp(a, b)  make_pair(a, b)
#define pb  push_back
#define eb  emplace_back

const int INF = 1<<28;
const int MOD = 1000000007;

int main(){
  int N, K; cin >> N >> K;
  string s; cin >> s;
  K--;
  s[K] += 0x20;
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>

using namespace std;

#define REP(i,n) for (int i = 0; i < n; i++)

int main() {

	string find, str[123];
	int N;
	char buf[32];

	scanf("%s", buf);
	find += buf;
	scanf("%d", &N);

	REP(i, N) {
		scanf("%s", buf);
		str[i] += buf;
		str[i] += buf;
	}

	int c = 0;
	REP(i, N) {
		if (str[i].find(find) != string::npos) c++;
	}

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

	return 0;
}

Measured memory_bytes: 2824
d, g = map(int, input().split())
test = []
point = []
for i in range(1, d+1):
    p, c = map(int, input().split())
    test.append([p, c])
    point.append([c + (p * i * 100), p])
inf = 10 ** 9
ans = inf
for i in range(2 ** d):
    b = bin(i)[2:]
    b = (d - len(b)) * "0" + b
    temp = 0
    calc = 0
    for j, bb in enumerate(b):
        if bb == "1":
            calc += point[j][0]
            temp += point[j][1]
    if calc >= g:
        ans = min(ans, temp)
    else:
        j_temp = b.rfind("0")
        if (g - calc) <= (test[j_temp][0] - 1) * (j_temp + 1) * 100:
            if (g - calc) % ((j_temp + 1) * 100) == 0:
                ans = min(ans, temp + ((g - calc) // ((j_temp + 1) * 100)))
            else:
                ans = min(ans, temp + ((g - calc) // ((j_temp + 1) * 100)) + 1)
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using ll = long long;

int main()
{
	int k;
	string s;
	cin >> k >> s;
	if (s.length() > k)
	{
		s = s.substr(0, k) + "...";
	}
	cout << s << endl;

}

Measured memory_bytes: 3600
#include<stdio.h>
     
    int main(void)
     {
        int N,i,sum=0;
        scanf("%d",&N);
        for(i=1;i<=N;i++)
          {
            sum=sum+i;
          }
       printf("%d",sum);
       rewind(stdin);
       getchar();
       return 0;
     }

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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()
#define endl "\n"

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

  int A,B;
  cin>>A>>B;
  cout<<max(0,A-2*B)<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <complex>
#include <bitset>
#include <functional>

using namespace std;
using ll=long long int;

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

    if (s == "AAA" | s == "BBB") {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (ll i = 0; i < (n); i++)
#define INF 1e9
#define MOD 1000000007
#define All(x) (x).begin(), (x).end()
typedef long long ll;
using namespace std;

int main(void){
    string S,T,U;
    int A,B;
    cin>>S>>T>>A>>B>>U;
    if(S==U)A--;
    else B--;
    cout<<A<<endl;
    cout<<B<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
//using ll = long long;
typedef long long ll;

int main(){
    int n;
    cin >> n;
    vector<string> s(n);
    rep(i,n) cin >> s[i];
    sort(s.begin(),s.end());
    int ans=1;
    rep(i,n-1){
        if(s[i]!=s[i+1]) ans++;
    }
    cout << ans << endl;

}


Measured memory_bytes: 9600
#include<iostream>
using namespace std;
int main(){
int n,i,j;
  cin >> n;
  for(i=1;i<=9;i++){
  	for(j=1;j<=9;j++){
 		if(i*j==n){
        cout << "Yes" << endl;
          return 0;
        }
  	}
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 384
/*
Author: Racer5x
 ***************************************   UNAUTHORISED COPYING OF CODE PROHIBITED   **********************************
*/
 
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#include<bits/stdc++.h>
#define int         long long
#define double      long double
#define pb          emplace_back
#define pf          emplace_front
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()
#define x           first
#define y           second
#define endl        '\n'
#define hell        998244353 
#define PI          3.141592653589
#define tezz        ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define MAX         2000000000000000000
#define M           1000000007
using namespace std;
 
signed main()
{
    tezz
    
    string s;
    int n;
    cin>>n>>s;

    if(n<3200) cout<<"red";
    else cout<<s;
} 

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define Task ""

using namespace std;
typedef long long ll;

signed main(void)
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen("A.INP", "r")){
        freopen("A.INP", "r", stdin);
        freopen("A.OUT", "w", stdout);
    }
    if (fopen(Task".in", "r")){
        freopen(Task".in", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    int n; cin >> n;
    vector<pair<int, int>> a(n);
    vector<int> res(n);
    for (int i=0; i<n; ++i){
        cin >> a[i].fi; a[i].se = i;
    }
    sort(a.begin(), a.end());
    for (int i=0; i<n; ++i){
        if (i < n / 2){
            res[a[i].se] = a[n / 2].fi;
        }
        else{
            res[a[i].se] = a[n / 2 - 1].fi;
        }
    }
    for (int i=0; i<n; ++i)
        cout << res[i] << '\n';
}


Measured memory_bytes: 4608
import java.util.*;

class Main{

    void solve(){
	Scanner sc = new Scanner(System.in);

	while(true){
	    int n1 = sc.nextInt(), n2 = sc.nextInt(), n3 = sc.nextInt();
	    int n4 = sc.nextInt(), n5 = sc.nextInt(), n6 = sc.nextInt();
	    if(n1==0 && n2==0 && n3==0 && n4==0 && n5==0 && n6==0) break;

	    int type1 = n1 + n4;
	    int type2 = n2 + n5;
	    int type3 = n3 + n6;

	    int max = 0;
	    for(int i=0; i<=6; i++){
		if(type1-i<0 || type2-i<0 || type3-i<0) continue;
		int sum = i + (type1-i)/3 + (type2-i)/3 + (type3-i)/3;
		max = Math.max(max, sum);
	    }

	    System.out.println(max);
	}
    }

    public static void main(String[] args){
	new Main().solve();
    }
}

Measured memory_bytes: 64836
#include<bits/stdc++.h>
using namespace std;
string s,t;
int ls,lt,ans=1e9;
int main(){
	cin>>s>>t;
	ls=s.size(),lt=t.size();
	for(int i=0;i<=ls-lt;i++){
		int cnt=0;
		for(int j=0;j<lt;j++)
			if(s[i+j]!=t[j])
				cnt++;
		ans=min(ans,cnt);
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 3584
#include<cstdio>
#include<queue>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{
    priority_queue<int,vector<int>,greater<int>> left,right;
    int n;
    int k;
    int x[100005];
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&x[i]);
    }
    ll ti=0x3f3f3f3f3f3f;
    for(int i=1;i+k-1<=n;++i)
    {
        int l=i,r=i+k-1;
        ti=min(ti,(ll)x[r]-x[l]+min(abs(x[l]),abs(x[r])));
    }
    printf("%lld\n",ti);
}


Measured memory_bytes: 512
// ABC 088 B- Card Game for Two

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

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

  vector<int> vec(N);
  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  // 得点を大きい順にする
  sort(vec.begin(), vec.end());
  reverse(vec.begin(), vec.end());

  // 偶数(Alice)と奇数(Bob)でそれぞれ点数を足し合わせる
  int pl = 0, mi = 0; // カウントする系なのは初期値設定しておこう
  for (int i = 0; i < N; i++) {
    if (i % 2 == 0) {
      pl += vec.at(i);
    }
    else {
      mi += vec.at(i);
    }
  }
  cout << pl - mi << endl;
}


Measured memory_bytes: 3592
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
 
//#include <x86intrin.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <bitset> 
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <iomanip>
#include <stack>
#include <map>
#include <set>
//#include <ordered_set>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
 
//using namespace __gnu_pbds;
using namespace std;
 
//template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
     
#define F first
#define S second           
#define lb lower_bound               
#define ub upper_bound
#define pb push_back
#define pf push_front    
#define ppb pop_back
#define mp make_pair                                     
#define bpp __builtin_popcountll                                                                                        
#define sqr(x) ((x) * (x)) 
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define in insert
#define ppf pop_front
#define endl '\n'
//#define int long long
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
 
const int mod = (int)1e9 + 7;
const int N = (int)3e5 + 123;
const ll inf = (ll)1e18 + 1;
 
const double pi = acos (-1.0);
const double eps = 1e-9;                  
const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};

int x[6];

inline void boost () {
   ios_base :: sync_with_stdio (0);
   cin.tie (0), cout.tie (0);
}
 
inline void Solve () {
   int pos = 0;
   for (int i = 1; i <= 5; i ++) {
      cin >> x[i];
      if (!x[i]) pos = i;
   }    
   cout << pos;
}               
 
signed main () {                                       
   #ifdef QWERTY
      freopen("input", "r", stdin);
   #endif
// freopen (".in", "r", stdin);    
// freopen (".out", "w", stdout);              
   boost ();
   int tt = 1;
   //cin >> tt;   
   while (tt --) {
      Solve ();
   }                                               
   return 0;      
}                   

Measured memory_bytes: 3584
#include<iostream>

using namespace std;

int main() {
	int a[101];
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	cout << a[n - 1];
	for (int j = 1; j < n; j++) {
		cout <<" "<< a[n - j -1];
	}
	cout << endl;
	return 0;
}



Measured memory_bytes: 3104
import java.util.Scanner;

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

		int n = scan.nextInt();
		int m = scan.nextInt();
		int l = scan.nextInt();
		int[][] detA = new int[n][m];
		int[][] detB = new int[m][l];

		for (int i = 0; i < detA.length; i++) {
			for (int j = 0; j < detA[i].length; j++) {
				detA[i][j] = scan.nextInt();
			}
		}

		for (int i = 0; i < detB.length; i++) {
			for (int j = 0; j < detB[i].length; j++) {
				detB[i][j] = scan.nextInt();
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < l; j++) {
				long sum = 0;
				for (int k = 0; k < m; k++) {
					sum += detA[i][k] * detB[k][j];
				}
				System.out.print(sum);
				if (j == l - 1)
					continue;
				System.out.print(" ");
			}
			System.out.println();
		}

		scan.close();
	}
}

Measured memory_bytes: 44880
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

//#define DEBUG_MODE
#ifdef DEBUG_MODE
#define dump(x) cout << #x << " : " << x << endl
#define LINE cout << "line : " << __LINE__ << endl
#define dumpV(v) cout << #v << " : ["; for(auto& t : v) cout << t << ", "; cout<<"]" << endl;
#define STOP assert(false);
#else
#define dump(x) ;
#define LINE 	;
#define dumpV(v);
#define STOP 	;
#endif

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fi<<", "<<a.se<<')';
    return out;
  }
}


int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};
auto isOutOfRange = [](int h, int w, int H, int W) {
	return h < 0 || h >= H || w < 0 || w >= W;
};

int merge(int y, int x) {return y * 50 + x;}
int getX(int yx) {return yx % 50;}
int getY(int yx) {return yx / 50;}

bool used[2510][2510];

int main(){
	int H, W;
	while(cin >> W >> H) {
		if(H == 0 && W == 0) break;
		rep(i, 2510) rep(j, 2510) used[i][j] = false;
		vector<string> sl(H), sr(H);
		rep(i, H) cin >> sl[i] >> sr[i];
		int sxl, syl, gxl, gyl;
		int sxr, syr, gxr, gyr;
		rep(i, H) rep(j, W) {
			if(sl[i][j] == 'L') syl = i, sxl = j;
			if(sl[i][j] == '%') gyl = i, gxl = j;
			if(sr[i][j] == 'R') syr = i, sxr = j;
			if(sr[i][j] == '%') gyr = i, gxr = j;
		}
		int startL = merge(syl, sxl), goalL = merge(gyl, gxl), startR = merge(syr, sxr), goalR = merge(gyr, gxr);
		queue<pii> q;
		pii p;
		q.push({startL, startR});
		used[startL][startR] = true;
		bool f = false;
		while(!q.empty()) {
			p = q.front(); q.pop();
			int xl = getX(p.fi), yl = getY(p.fi);
			int xr = getX(p.se), yr = getY(p.se);

			pii l = {xl, yl}, r = {xr, yr};
			dump(l);
			dump(r);

			rep(i, 4) {
				int nxl = xl + dx[i], nyl = yl + dy[i];
				int nxr = xr + dx[(i+2)%4], nyr = yr + dy[i];
				if(isOutOfRange(nyl, nxl, H, W) || sl[nyl][nxl] == '#') nyl = yl, nxl = xl;
				if(isOutOfRange(nyr, nxr, H, W) || sr[nyr][nxr] == '#') nyr = yr, nxr = xr;
				int nxtL = merge(nyl, nxl), nxtR = merge(nyr, nxr);
				if(nxtL == goalL && nxtR == goalR) {
					f = true;
					break;
				}
				if(nxtL == goalL || nxtR == goalR || used[nxtL][nxtR]) continue;
				q.push({nxtL, nxtR});
				used[nxtL][nxtR] = true;
			}
			if(f) break;
		}
		cout << (f ? "Yes" : "No") << endl;
	}
	return 0;
}

Measured memory_bytes: 9700
N,M=map(int,input().split())
A=list(map(int,input().split()))
BC=[[0,0] for i in range(M)]
for i in range(M):
    BC[i][0],BC[i][1]=map(int,input().split())

A=sorted(A)
BC=list(sorted(BC,reverse=True,key=lambda x: x[1]))

i=0
for B,C in BC:
    for j in range(i,min(N,i + B)):
        if A[j] < C:
            A[j] = C
            #B枚分先を飛ばす BCはCに関して降順のため問題ない
    i = i + B
 
print(sum(A))

Measured memory_bytes: 26412
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
#include <tuple>

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define co(x) cout << (x) << "\n"
#define ll long long
#define pb push_back
#define Never
#define To

using namespace std;

int main(){

	cin.tie(0);
	ios::sync_with_stdio(false);

	string s[3];

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

	for(int i = 0; i < 3; i++){
		cout << s[i][i];
	}
	cout << endl;

	Never To return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long n;
int main(){
cin>>n;
for(long i=1;i<=3500;i++){
for(long j=1;j<=i;j++){
if(4*i*j-n*i-n*j<=0) continue;
if((n*i*j)%(4*i*j-n*i-n*j)==0){
cout<<i<<" "<<j<<" "<<(n*i*j)/(4*i*j-n*i-n*j)<<endl;
return 0;
}
}
}
}


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

int main(){
  string S;
  cin >> S;
  
  reverse(S.begin(),S.end());
  
  string divide[4] = {"dream", "dreamer", "erase", "eraser"};
  for(int i=0;i<4;i++){
    reverse(divide[i].begin(),divide[i].end());
  }
  
  bool can = true;
  for(int i=0;i<S.size();){
    bool can2 = false;
    for(int j=0;j<4;j++){
      string d = divide[j];
      if(S.substr(i,d.size())==d){
        i +=  d.size();
        can2 = true;
      }
    }
    
    if(can2==false){
      can = false;
      break;
    }
  }
  if(can==true){
    cout << "YES" << "\n";
  }else{
    cout << "NO" << "\n";
  }  
}

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

int main() {
  string S;
  cin>>S;
  string ans="AC";
  if(S.at(0)!='A'){
    ans="WA";
  }
  int test=0;
  for(int i=1;i<S.size();i++){
    if(isupper(S.at(i))){
      if(i==1||i==S.size()-1||S.at(i)!='C'){
        ans="WA";
      }
      test++;
    }
       }
       if(test!=1){
         ans="WA";
       }
       cout<<ans<< endl;
       }
        


Measured memory_bytes: 256
n = int(input())

base = ['a' for i in range(n)]

end = ['z' for i in range(n)]

def sorted_k_partitions(seq, k):
    n = len(seq)
    groups = []  # a list of lists, currently empty

    def generate_partitions(i):
        if i >= n:
            yield list(map(tuple, groups))
        else:
            if n - i > k - len(groups):
                for group in groups:
                    group.append(seq[i])
                    yield from generate_partitions(i + 1)
                    group.pop()

            if len(groups) < k:
                groups.append([seq[i]])
                yield from generate_partitions(i + 1)
                groups.pop()

    result = generate_partitions(0)

    # Sort the parts in each partition in shortlex order
    result = [sorted(ps, key = lambda p: (len(p), p)) for ps in result]
    # Sort partitions by the length of each part, then lexicographically.
    result = sorted(result, key = lambda ps: tuple(map(len, ps)) + (ps,))

    return result

seq = [i+1 for i in range(n)]

# print(seq)

res = []

for k in seq:
    for groups in sorted_k_partitions(seq, k):
        temp = ['a' for i in range(n)]
        tmp = []
        tmp = list(groups)
        tmp.sort()
        # print(tmp)
        counter = 0
        for t in tmp:
            for e in t:
                temp[e-1] = chr(ord('a') + counter)
            counter += 1
        # print('after')
        # print(temp)
        res.append(''.join(temp))

res.sort()

for r in res:
    print(r)


Measured memory_bytes: 33292
"Binary Indexed Tree"
"""
- iが与えられたときa1~aiまでの和を計算する O(log n)
- iとxが与えられたときai += x とする O(log n)
"""
# BIT: Binary Indexed Tree (1-indexed), 0-indexだと困るので。
# A1~Aiまでの和 O(logN)


def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)  # 次に求める区間のindexは今見ているindexから今見ている区間の長さ(これはidx&(-idx)で求めることができる)を引くことでindexを求めることができる
    return res_sum


# Ai += x  O(logN)
def BIT_updata(idx, x):
    while idx <= N:
        BIT[idx] += x
        idx += (idx&(-idx))  # 次に更新すべき区間のindexは今見ているindexに今見ている区間の長さを足すことでindexを求めることができる
    return


# n = 8
# BIT = [0]*(n+1)  # 最初に0で初期化する
# a = [1, 2, 3, 4, 5, 6, 7, 8]
# for i, e in enumerate(a):
#     BIT_updata(i+1, e)
#
#
# # A0~A2の和: 6
# print(BIT_query(3))  # ここのアクセスは1-indexで考えている
# # A3~A6の和: 18
# print(BIT_query(6)-BIT_query(2))  # ここのアクセスは1-indexで考えている
# print(BIT)

# BIT_queryで10~15マス前の和を現在のところに加える
N, K = map(int, input().split())
move = []
for _ in range(K):
    l, r = map(int, input().split())
    move.append([l, r])
MOD = 998244353
BIT = [0]*(N+1)  # スタート地点1~ゴール地点NまでのN個 (1-indexed)
BIT_updata(1, 1)
for i in range(2, N+1):
    for l, r in move:
        # lマス前からrマス前までの区間和を現在のマスに加える
        BIT_updata(i, (BIT_query(i-l)-BIT_query(i-r-1))%MOD)
ans = BIT_query(N) - BIT_query(N-1)
print(ans%MOD)
# BIT_query(N-10) - BIT_query(N-15)を現在のところにタス
# いや，微妙に違う?


Measured memory_bytes: 75624
#include<bits/stdc++.h>
using namespace std;
char s[105];
int k, p;
int main(){
	cin>> k>> s;
	p= strlen(s);
	if(k>=p){
		cout<< s;
	}else{
		for(int i=0; i<k; i++){
			cout<< s[i];
		}
		cout<< "...";
	}
	return 0;
} 

Measured memory_bytes: 3552
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define INF 1000000
using namespace std;
int main()
{
    int q;
    cin >> q;
    long long cnt1 = 0, cnt2 = 0;
    rep(i, q)
    {
        long long p, n;
        char c;
        scanf("%d %c %d", &p, &c, &n);
        //cin >> p >> c >> num;
        if (c == '(')
            cnt1 += n;
        if (c == ')')
            cnt2 += n;
        if (cnt1 == cnt2)
            printf("Yes\n");
        //cout << "Yes" << endl;
        else
            printf("No\n");
        //cout << "No" << endl;
    }
    return 0;
}


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

#define int long long

signed main(void){
    int n; cin >> n;
    vector<int>a(101,0);
    for(int i=0;i<n;i++){
        int x; cin >> x;
        for(int j=1;j<=100;j++){
            a[j] += pow(j-x,2);
        }
    }
    int ans = 1e10;
    for(int i=1;i<a.size();i++){
        if(a[i]<ans) ans = a[i];
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
  char a;
  cin >> a;

  if (a == 'a'||a == 'i'||a == 'u'||a == 'e'||a == 'o') {
    cout << "vowel" << endl;
}
else {
cout << "consonant" << endl;
}
}


Measured memory_bytes: 256
import Data.List

main :: IO ()
main = do
  n <- readLn :: IO Int
  as <- map read . words <$> getLine :: IO [Int]
  print $ solve as
  return ()

solve :: [Int] -> Int
solve xs = sum $
           map f $
           group $ sort xs
  where
    f [] = 0
    f ys@(y:_)
      | y == n = 0
      | n > y = n-y
      | n < y = n
        where
          n = length ys


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

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

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

#define INF 1e16
#define mod 1000000007

#define PI acos(-1.0)

struct point{
  ll x,y;
  long double arg;
};

long double calc(ll x,ll y){
  return x*x+y*y;
}

ll n;
vector<point> ps;

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

  cin>>n;
  rep(i,n){
    ll x,y;
    cin>>x>>y;
    if(x==0&&y==0)continue;
    ps.push_back((point){x,y,atan2(y,x)});
  }
  n=ps.size();

  sort(all(ps),[](const point& a,const point& b){
    return a.arg < b.arg;
  });

  rep(i,n)ps.push_back(ps[i]);

  long double res=0;
  ll j=0;
  ll X=0,Y=0;
  rep(i,n){
    long double crt=calc(X,Y);
    maxch(res,calc(X,Y));
    while(j<i+n){
      X+=ps[j].x;
      Y+=ps[j].y;
      if(crt>calc(X,Y)){
        X-=ps[j].x; Y-=ps[j].y;
        break;
      }
      j++;
      maxch(res,calc(X,Y));
      crt=calc(X,Y);
    }
    X-=ps[i].x; Y-=ps[i].y;
  }
  printf("%.12Lf\n", sqrt(res));

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
using namespace std;
int f(string s, string t)
{
  int ans = 0;
  for (char c = 'a'; c <= 'z'; c++)
  {
    bool founds = false, foundt = false;
    rep(i, s.size())
    {
      if (s[i] == c)
      {
        founds = true;
      }
    }
    rep(i, t.size())
    {
      if (t[i] == c)
      {
        foundt = true;
      }
    }
    if (founds && foundt)
      ans++;
  }
  return ans;
}

int main()
{
  int N;
  string S;
  cin >> N >> S;
  int ans = 0;
  rep(i, N + 1)
  {
    int tmp = f(S.substr(0, i), S.substr(i));
    ans = max(ans, tmp);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
S = list(input())
N = len(S)
A = S.count("a")
B = S.count("b")
C = S.count("c")

if  N % 3 == 0:
	if A == B and B == C:
		print("YES")
	else:
		print("NO")
else:
	n = int(N // 3)
	if n <= A and A <= n + 1 and n <= B and B <= n + 1 and n <= C and C <= n + 1:
		print("YES")
	else:
		print("NO")

Measured memory_bytes: 3956
#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
const int MOD = 1e9+7;
int p[2*N][2*N];
int C[4*N][2*N];
int main() {
	for (int i=0;i<4*N;i++)
		for (int j=0;j<=min(i,2*N-1);j++)
			if (i == j) C[i][j] = 1;
			else if (j == 0) C[i][j] = 1;
			else C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD; 
	int n;
	int ans = 0;
	int ans2 = 0;
	scanf("%d",&n);
	for (int i=0;i<n;i++) {
		int x,y;
		scanf("%d %d",&x,&y);
		p[N-x][N-y]++;
		p[N+x][N+y]++;
		ans = (ans + C[2*(x+y)][2*x]) % MOD;
	}
	for (int i=1;i<2*N;i++)
		for (int j=1;j<2*N;j++) {
			if (i>N && j>N && p[i][j]) {
				ans2 = ((1ll*p[i][j]*((p[i-1][j] + p[i][j-1]) % MOD)) % MOD + ans2) % MOD;
				p[i][j] = (p[i-1][j] + p[i][j-1]) % MOD;
			}
			else p[i][j] = (1ll*p[i-1][j] + p[i][j-1] + p[i][j]) % MOD;
		}
	ans = (ans2+MOD-ans) % MOD;
	if (ans % 2) ans += MOD;
	printf("%d\n",ans/2);
	return 0;
}

Measured memory_bytes: 172032
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define pii pair <ll,ll>
#define vl vector <ll>
#define vp vector <pair<ll,ll>>
#define sort(x) sort(x.begin(), x.end())
using namespace std;
ll ans(ll h)
{
    if(h == 1)
        return 1;
    return 2*ans(h/2)+1;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll h;
    cin>>h;
    cout<<ans(h);    
    return 0;
}


Measured memory_bytes: 256
n = int(input())
s = input()

"""
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
"""
# gagsg
r = 0
g = 0
b = 0
for i in range(n):
    if s[i] == 'R':
        r += 1
    elif s[i] == 'G':
        g += 1
    else:
        b += 1
ans = r*g*b

for i in range(n-2):
    for j in range(i+1, n-1):
        k = 2 * j - i
        if k < n:
            if s[i] == s[j]:
                continue
            if s[j] == s[k]:
                continue
            if s[k] == s[i]:
                continue
            ans -= 1
print(ans)


Measured memory_bytes: 67644