akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef set<int> si;
typedef map<string, int> msi;
typedef greater<int> gt;
typedef priority_queue<int, vector<int>, gt> minq;
typedef long long ll;
const ll INF = 1e18L + 1;

//clang++ -std=c++11 -stdlib=libc++ 
ll Q,P;
int N;
vector<ll> nums;
bool flag[10];

void dfs(ll a, int len) {
  if (len == N) {
    nums.push_back(a); 
    return;
  }
  for (int i=1; i<=N; i++) {
    if (flag[i]) continue;
    flag[i] = true;
    dfs(a*10+i, 1+len);
    flag[i] = false;
  }
}


int main() {
  cin>>N;
  rep(i,N) {
    int a ;cin>>a;
    P*=10; P+=a;
  }
  rep(i,N) {
    int a; cin>>a;
    Q*=10; Q+=a;
  }
  dfs(0,0);
  int a=0,b=0;
  for (int i=0; i<nums.size();i ++)  {
    if (nums[i]==P) a=i;
    if (nums[i]==Q) b=i;
  }
  sort(nums.begin(), nums.end());
  cout << abs(a-b) << endl;
  return 0;
}

Measured memory_bytes: 892
#include<stdio.h>
int main()
{
    int a,b,c,s,ans,t;
    scanf("%d%d%d",&a,&b,&c);
    if(a>b)
       t=a,a=b,b=t;
    if(a>c)
        t=a,a=c,c=t;
    if(b>c)
        t=b,b=c,c=t;
    if((2*c-a-b)%2)
        s=c+1;
    else
        s=c;
    ans=(3*s-a-b-c)/2;
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#ifdef _DEBUG_
	#define debug(...) printf(__VA_ARGS__)
#else
	#define debug(...) (void)0
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

const int MAXN = 1e5 + 100;
struct E {
	int a, b, c, son;
} e[MAXN];
vector<int> ei[MAXN];
int sz[MAXN];
void DFS(int x, int p) {
	sz[x] = 1;
	for(int i : ei[x]) {
		int u = x ^ e[i].a ^ e[i].b;
		if(u == p) continue;
		e[i].son = u;
		DFS(u, x);
		sz[x] += sz[u];
	}
}

bool fine[MAXN];

int main() {
	int N;
	scanf("%d", &N);
	for(int i = 1; i < N; i++) {
		int A, B, C;
		scanf("%d%d%d", &A, &B, &C);
		e[i] = {A, B, C, 0};
		ei[A].PB(i);
		ei[B].PB(i);
	}
	DFS(1, 0);
	int spe = -1;
	for(int i = 1; i < N; i++) {
		if(sz[e[i].son] * 2 == N) {
			spe = i;
			break;
		}
		if(sz[e[i].son] * 2 < N) {
			int u = e[i].son;
			fine[u] = true;
		}
		else {
			int u = e[i].son ^ e[i].a ^ e[i].b;
			fine[u] = true;
		}
	}
	ll ans = 0;
	if(spe != -1) {
		for(int i = 1; i < N; i++) {
			if(i == spe) {
				ans += 1ll * (N - 1) * e[i].c;
				continue;
			}
			int x = sz[e[i].son];
			int y = N - x;
			ans += 1ll * min(x, y) * 2 * e[i].c;
		}
	}
	else {
		int mn = 1e9;
		int tar = 0;
		for(int i = 1; i <= N; i++)
			if(!fine[i]) {
				tar = i;
				break;
			}
		for(int i = 1; i < N; i++) {
			int x = sz[e[i].son];
			int y = N - x;
			ans += 1ll * min(x, y) * 2 * e[i].c;
			if(e[i].a == tar || e[i].b == tar)
				mn = min(mn, e[i].c);
		}
		ans -= mn;
	}
	cout << ans << endl;
	return 0;
}


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

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

#ifndef INPUTS_DIR
#define INPUTS_DIR "./"
#endif

using namespace std;


int w[3] = {3, 5, 7};
long long ans;

int dfs(ll x, ll n, int bit) {
    if (x > n) return 0;
    if (bit == 7) ans++;
    for (int i = 0; i < 3; i++) dfs(x * 10 + w[i], n, bit | (1 << i));
};

void solve(ll N) {
    dfs(0, N, 0);
    cout << ans << endl;
}


void main_(istream &cin) {
    ll N;
    cin >> N;
    solve(N);
}

int main() {
#ifdef INTELLIJ
    ifstream ifs(string(INPUTS_DIR) + "in_1.txt");
    if (ifs.is_open()) {
        main_(ifs);
        ifs.close();
    } else {
        cerr << "Error: no input." << endl;
    }
#else
    ios::sync_with_stdio(false);
    cin.tie(0);
    main_(cin);
#endif
}





Measured memory_bytes: 256
using System;
using System.Linq;

class B
{
	static void Main()
	{
		var s = Console.ReadLine();
		Console.WriteLine(s.Where((c, i) => i % 2 == 0).All(c => c != 'L') && s.Where((c, i) => i % 2 == 1).All(c => c != 'R') ? "Yes" : "No");
	}
}


Measured memory_bytes: 13268
#!/usr/bin/env python3
import sys
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            return None

        s, t, w = edge
        self.E[s].append([t, w])
        return True


def BellmanFord(g: Graph, s):
    """ベルマンフォード法によって最短経路を求める
    """
    N = g.N
    dist = [INF]*N
    dist[s] = 0
    prev = [None]*N

    # 辺の緩和
    for i in range(N):
        for from_ in range(N):      # ここの２重ループはO(M)
            for to_, weight in g.E[from_]:
                if dist[to_] > dist[from_] + weight:
                    dist[to_] = dist[from_] + weight
                    prev[to_] = from_
                    if i == N-1 and to_ == N-1:
                        return None, None

    return dist, prev


def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    g = Graph(N)
    for f, t, w in zip(a, b, c):
        g.add_edge([f-1, t-1, -w])

    dist, prev = BellmanFord(g, 0)

    if dist == None:
        print("inf")
    else:
        print(-dist[N-1])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    c = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, M, a, b, c)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3700
def stones(N: int, S: str)->int:
    # 左から見た黒石の個数の累積和と
    # 右から見た白石の個数の累積和を保持し
    # その和が最小となる位置を探す。
    black, white = [0] * (N+1), [0] * (N+1)

    for i, c in enumerate(S):
        black[i+1] = black[i]
        if c == '#':
            black[i+1] += 1

    for i, c in enumerate(S[::-1]):
        white[N-i-1] = white[N-i]
        if c == '.':
            white[N-i-1] += 1

    # print(black)
    # print(white)

    return min(black[i] + white[i+1] for i in range(N))


if __name__ == "__main__":
    N = int(input())
    S = input()
    ans = stones(N, S)
    print(ans)


Measured memory_bytes: 12876
// add(s,t,x): a[s],a[s+1],...,a[t] にxを加算する
// get(i): a[i]の値を出力する
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int sqrtN = 512;

struct SqrtDecomposition{

    int N, K;             //データ数, バケット数
    vector<int> data;
    vector<int> bucketAdd;
    SqrtDecomposition(int n) : N(n) {
        K = (N + sqrtN - 1) / sqrtN;
        data.assign(K * sqrtN, 0);
        bucketAdd.assign(K, 0);
    }

    // [s, t)
    void add(int s, int t, int x){

        for(int k = 0; k < K; k++){
            int l = k * sqrtN;
            int r = (k + 1) * sqrtN;

            if(r <= s || t <= l) continue;
            
            if(s <= l && r <= t) bucketAdd[k] += x;
            else{
                for(int i = max(s, l); i < min(t, r); i++){
                    data[i] += x;
                }
            }
        }
    }

    int get(int i){
        int k = i / sqrtN;
        return data[i] + bucketAdd[k];
    }
};

signed main(){
    
    int N, Q;
    cin >> N >> Q;
    SqrtDecomposition decomp(N);
    while(Q--){
    int c; cin >> c;
    if(c == 0){
        int s, t, x; cin >> s >> t >> x;
        decomp.add(s, t + 1, x);
    }else{
        int i; cin >> i;
        cout << decomp.get(i) << endl;
    }
  }

  return 0;
}


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

using namespace std;

int main()
{
	int n , k, x, ans=0;
	cin >> n >> k;
	multiset < int > v;
	while(n--){
		cin >> x;
		v.insert(x);
	}
	x=0;
	for(auto MMB : v){
		if(x == k) break;
		ans += MMB;
		x++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3680
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REV(c) reverse(ALL(c))
#define sz(v) (int)v.size()
#define endl '\n'
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
template<class T> inline void prn(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << ' ';}
template<class T> inline void printv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << (i == n - 1 ? endl : ' ');}
template<class T> inline void printvv(vector<vector<T>>& v) {for (auto u : v) printv(u);}
template<class T> inline void printlnv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << endl;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

void solve() {
    int h, w, a, b;
    cin >> h >> w >> a >> b;
    REP(i, h) {
        REP(j, w) {
            if (i < b) {
                if (j < a) cout << 0;
                else cout << 1;
            } else {
                if (j < a) cout << 1;
                else cout  << 0;
            }
        }
        cout << endl;
    }
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
#define LL long long
#define ULL unsigned long long

int a[maxn];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    if(k>a[n]){
        puts("IMPOSSIBLE");
        return 0;
    }
    if(n==1){
        if(a[1]!=k)
            puts("IMPOSSIBLE");
        else 
            puts("POSSIBLE");
        return 0;
    }

    int G=__gcd(a[1],a[2]);
    for(int i=3;i<=n;i++){
            G=__gcd(G,a[i]);
    }
    if(G==1)
        puts("POSSIBLE");
    else {
        if(k%G==0){
            puts("POSSIBLE");
        }
        else
            puts("IMPOSSIBLE");
    }
    return 0;
}


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

int main() {
  int n;
  cin >> n;
  
  vector<long long> v(n);
  
  for (int i = 0; i < n; i++)
    cin >> v.at(i);
  
  long long mod = 1000000007;
  long long sum = 0;
  
  for (int i = 0; i < n; i++) {
    sum += v.at(i);
    sum %= mod;
  }
  
  long long ans;
  
  ans = sum * sum % mod;
  
  for (int i = 0; i < n; i++) {
    ans -= (long long)v.at(i) * v.at(i) % mod;
  }
  
  while (ans < 0) ans += mod;
    
  ans *= (mod + 1) / 2;
  
  cout << ans % mod << endl;
}
  

Measured memory_bytes: 4756
#include <iostream>

using namespace std;

bool two(const string& s) {
  for (int i = 0; i < (int)s.length() - 1; ++i) {
    if (s[i] == s[i+1]) {
      cout << i + 1 << ' ' << i + 2 << endl;
      return true;
    }
  }
  return false;
}

bool three(const string &s) {
  for (int i = 0; i < (int)s.length() - 2; ++i) {
    if (s[i] == s[i+2]) {
      cout << i + 1 << ' ' << i + 3 << endl;
      return true;
    }
  }
  return false;
}

int main() {
  string s;
  while (cin >> s) {
    if (!(two(s) || three(s))) {
      cout << "-1 -1" << endl;
    }
  }
}


Measured memory_bytes: 512
#include<iostream>
#include<queue>
#include<cstdio>
#include<cmath>
#define inf 100000007
using namespace std;

struct State{
  int speed,now,before;
  double time;
  State(double time,int speed,int now,int before):
    time(time),speed(speed),now(now),before(before){}
  bool operator<(State S)const{
    return S.time < time;
    }
};

int main()
{
  int n,m,s,g,a,b,d,l;
  int dis[31][31],lim[31][31],S[3]={-1,0,1};
  double dp[31][31][31],eps=1e-8; 

  while(1){
    cin>>n>>m;
    if(n+m==0)break;
    cin>>s>>g;
    s--;g--;
    for(int i=0;i<31;i++){
      for(int j=0;j<31;j++){
	dis[i][j]=inf;
	lim[i][j]=inf;
	for(int k=0;k<31;k++)dp[i][j][k]=inf;
      }
    }
    for(int i=0;i<m;i++){
      cin>>a>>b>>d>>l;
      a--;b--;
      dis[a][b]=d;
      dis[b][a]=d;
      lim[a][b]=l;
      lim[b][a]=l;
    }

    double ans=inf;
    priority_queue<State> pq;
    pq.push(State(0,0,s,s));
    dp[s][s][0]=0;
    while(!pq.empty()){
      State u=pq.top();
      pq.pop();
      //  cout<<u.now<<" "<<u.before<<endl;
      if(u.now==g && u.speed==1){
	ans=min(u.time,ans);
	continue;
      }
      if(u.time > dp[u.before][u.now][u.speed]+eps)continue;
      /*
      printf("%.10f",u.f.f);
      cout<<" "<<u.f.s<<" "<<u.s.f<<" "<<u.s.s<<endl;
      */
      for(int i=0;i<n;i++){
	if(i==u.now)continue;
	if(i==u.before)continue;
      	if(dis[u.now][i]==inf)continue;
	for(int k=0;k<3;k++){
	  int speed = u.speed+S[k];
	  if( speed<1 || 30<speed )continue;
	  if( lim[u.now][i] < speed )continue;
	  double time=(double)dis[u.now][i]/(double)speed;
	  if( dp[u.now][i][speed] < time + u.time+eps)continue;
	  dp[u.now][i][speed] = time + u.time;
	  pq.push(State(time+u.time,speed,i,u.now));
	}
      }
    }
    if(ans>=inf-1)cout<<"unreachable"<<endl;
    else printf("%.6f\n",ans);
  }
  return 0;
}

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

int main(void){
    string s;
    cin>>s;
    for(int i=s.size()/2-1;i>0;i--){
        if(s.substr(0,i)==s.substr(i,i)){
            cout<<(i*2)<<endl;
            break;
        }
    }
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

ll sq(ll num) { return num*num; }
ll mod_pow(ll x, ll n) {
	if (n == 0)return 1;
	if (n == 1)return x%MOD;
	ll res = sq(mod_pow(x, n / 2));
	res %= MOD;
	if (n % 2 == 1) {
		res *= x;
		res %= MOD;
	}
	return res;
}
ll mod_add(ll a, ll b) { return (a + b) % MOD; }
ll mod_sub(ll a, ll b) { return (a - b + MOD) % MOD; }
ll mod_mul(ll a, ll b) { return a*b % MOD; }

string s;

int main(){
	cin >> s;
	ll cnt = 0;
	ll ans = 0;
	bool f = 0;
	rep(i,s.size()){
		if(s[i] == 'B')f = 1;
	}
	if(!f){
		cout << 0 << endl;
		return 0;
	}
	rep(i,s.size()){
		if(s[i] == 'W'){
			ans += (i - cnt);
			cnt++;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 640
using System;

namespace ABC095_a
{
    class Program
    {
        static void Main(string[] args)
        {
            string array = Console.ReadLine();
            int count = 0;
            for (int i = 0; i < array.Length; i++)
            {
                char a = array[i];
                if(a == 'o')
                {
                    count++;
                }

            }
            int answer = 700 + count * 100;
            Console.WriteLine(answer);
           
            
        }
    }
}


Measured memory_bytes: 13140
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
typedef complex<double> P;

int pls[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31, 31};

int calc(int y, int m, int d){
  --y;
  int res = (y / 4 - y / 100 + y / 400) + y * 365 + d;
  ++y;
  if((!(y % 4) && (y % 100 || !(y % 400))) && (m >= 3)) ++res;
  REP(i, m) res += pls[i];
  return res;
}

int main() {
  int y1, m1, d1, y2, m2, d2;
  while(cin >>y1 >>m1 >>d1 >>y2 >>m2 >>d2 && (y1 >= 0 && m1 >= 0 && d1 >= 0 && y2 >= 0 && m2 >= 0 && d2 >= 0)) cout <<calc(y2, m2, d2) - calc(y1, m1, d1) <<endl;
  return 0;
}

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

typedef long long ll;

int N;
vector<int> P;

void input_init(void) {
	cin >> N;
	P.resize(N + 1, 2);
	P[0] = 0;	P[1] = 1;
	for (int i = 2; i <= N / 2; ++i) {
		for (int j = 2 * i; j <= N; j += i)
			++(P[j]);
	}
}

ll calcu(void) {
	ll sum = (ll)0;
	for (int i = 1; i <= N; ++i)
		sum += (ll)i * P[i];
	return sum;
}

int main(void) {
	input_init();
	ll ans = calcu();
	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 42304
#ライブラリの読み込み
import math

#入力値の格納
n,k = map(int,input().split())
members = input().split()

#計算用カウンタの初期化
i = 0 #試行回数
p = 0 #不合格の人数

#身長との比較
while i < n:
    if int(members[i]) < k:
        p += 1
    i += 1

#表示
print(n-p)


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

using namespace std;
#define booster ios_base::sync_with_stdio(false); cin.tie(NULL);


void solve() {

     int n;
     cin>>n;
     vector<long long int>a(n);

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

     if(n<=2)  { cout<<"0"<<endl; return ;}

     long long int ans=0;
     sort(a.begin(),a.end());

     for(int i=0;i<=n-3;i++) {
         for(int j=i+1;j<=n-2;j++) {
             for(int k=j+1;k<=n-1;k++) {
                 if(a[i]!=a[j] && a[j]!=a[k] && a[i]!=a[k]) {
                     if(a[i]+a[j] > a[k]) ans++;
                 }
             }
         }
     }
     cout<<ans<<endl;




}


int main() {

    booster;
#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif


    int t;
    t = 1;


    while (t--) solve();


    return 0;
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
#define ll long long
#define pii_ pair<int,int>
#define mp_ make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define show1(a) cout<<#a<<" = "<<a<<endl
#define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl
using namespace std;
const ll INF = 1LL<<60;
const int inf = 1<<30;
const int maxn = 2e5+5;
inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}

ll n,a,b,c,d;
map<ll,ll> rec;
ll dfs(ll k)
{
    if(rec.count(k)) return rec[k];
    if(k==1){
        return d;
    }
    rec[k] = INF;
    if(k<=INF/d) rec[k] = min(rec[k],k*d);
    rep(i,-4,4){
        if(k+i>0 && (k+i)%5==0){
            ll tmp = dfs((k+i)/5);
            if(tmp>INF-c-d*abs(i)) continue;
            rec[k] = min(rec[k],tmp+c+d*abs(i));
        }else if(k+i==0){
            rec[k] = min(rec[k],abs(i)*d);
        }
    }
    rep(i,-2,2){
        if(k+i>0 && (k+i)%3==0) {
            ll tmp = dfs((k+i)/3);
            if(tmp>INF-b-d*abs(i)) continue;
            rec[k] = min(rec[k],tmp+b+d*abs(i));
        }else if(k+i==0){
            rec[k] = min(rec[k],abs(i)*d);
        }
    }
    rep(i,-1,1){
        if(k+i>0 && (k+i)%2==0) {
            ll tmp = dfs((k+i)/2);
            if(tmp>INF-a-d*abs(i)) continue;
            rec[k] = min(rec[k],tmp+a+d*abs(i));
        }else if(k+i==0){
            rec[k] = min(rec[k],abs(i)*d);
        }
    }
    return rec[k];
}

int main()
{
    fastio();
    int _;
    for(cin>>_;_;_--){
        rec.clear();
        cin>>n>>a>>b>>c>>d;
        cout<<dfs(n)<<endl;
    }
    return 0;
}


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

typedef long long LL;
LL h, w, n, ans[10];
LL dx[3] = {-2, -1, 0};
LL dy[3] = {-2, -1, 0};
map <LL, LL> mp;

void add (LL x, LL y)
{
	LL tx, ty;
	for (int i = 0; i < 3; ++i)
		for (int j = 0; j < 3; ++j)
		{
			tx = x + dx[i];
			ty = y + dy[j];
			if(tx < 1 || ty < 1 || tx > h - 2 || ty > w - 2)
				continue;
			++mp[(tx - 1) * (w - 2)+ty];
		}
}

int main ()
{
	scanf ("%lld%lld%lld", &h, &w, &n);
	for (int i = 1; i <= n; ++i)
	{
		LL x, y;
		scanf ("%lld%lld", &x, &y);
		add (x, y);
	}
	ans[0] = (h - 2) * (w - 2);
	for (map <LL, LL>::iterator it = mp.begin(); it != mp.end(); ++it)
		++ans[it -> second], --ans[0];
	for (int i = 0; i <= 9; ++i)
		printf ("%lld\n", ans[i]);
	return 0;
}

Measured memory_bytes: 56448
N = int(input())
an = list(map(int, input().split()))

ans = 0
right = 0
arith_sum = 0
for left in range(N):
    while right < N and arith_sum ^ an[right] == arith_sum + an[right]:
        arith_sum += an[right]
        right += 1
    ans += right - left
    arith_sum -= an[left]

print(ans)

Measured memory_bytes: 23560
// A - Grouping
#include <bits/stdc++.h>
using namespace std;

int main(){
	vector<int> group = {0,1,3,1,2,1,2,1,1,2,1,2,1};//1_origin
	int x,y; cin>>x>>y;
	puts(group[x] == group[y]? "Yes":"No");

}

Measured memory_bytes: 256
import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] dp = new int[100001];

		dp[0] = 0;

		for (int i = 1; i <= 100000; i++) {
			// 1円単位
			dp[i] = i;

			// 6円 36円 216円 1296円 7776円 46656円単位
			int cost = 1;
			while (cost <= i && 6 <= i) {
				dp[i] = Math.min(dp[i], dp[i - cost] + 1);
				cost *= 6;
			}

			// 9円 81円 729円 6561円 59049円単位
			cost = 1;
			while (cost <= i && 9 <= i) {
				dp[i] = Math.min(dp[i], dp[i - cost] + 1);
				cost *= 9;
			}

		}

		System.out.println(dp[N]);
		sc.close();
	}

}


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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);  
	
	string s; cin >> s;
	stack<char> t;
	for(int i = 0 ; i < s.size(); i++){
		if(s[i] == 'S') t.push(s[i]);
		else if (t.empty() || (t.top() == 'T' && s[i] == 'T')) t.push(s[i]);
		else if (s[i] == 'T' && t.top() == 'S') t.pop();
	}
	cout << t.size() << endl;
	return 0;	
}
  

Measured memory_bytes: 720
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()
A = III()
B = III()

def index_sort(A):
    a = []
    for i,x in enumerate(A):
        a.append([i,x])
    asort = sorted(a,key=lambda x: x[1])
    return [asort[i][0] for i in range(len(a))]

A2 = sorted(A)
B2 = sorted(B)

for i in range(N):
    if A2[i]>B2[i]:
        print('No')
        exit()

Aindex = index_sort(A)
Bindex = index_sort(B)
move = [0]*N
for i in range(N):
    move[Aindex[i]] = Bindex[i]

now = 0
for i in range(N):
    if move[now]==0 and i!=N-1:
        print('Yes')
        exit()
    now = move[now]

for i in range(N-1):
    if B2[i]>=A2[i+1]:
        print('Yes')
        exit()

print('No')

Measured memory_bytes: 102640
#include <iostream>
#include <string>
#include <vector>

using namespace std;

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

  vector <int> r(N, 0);
  vector <int> l(N, 0);

  int a = 0;
  for(int i=0;i<N;i++ )
    {
      l[i] = a;
      if( S[i] == 'W' )
	a++;
    }
  a = 0;
  for(int i=N-1;i>-1;i-- )
    {
      r[i] = a;
      if( S[i] == 'E' )
	a++;
    }

  a = N;
  for( int i=0;i<N;i++ )
    a = min(a, r[i]+l[i]);

  cout << a << endl;
}


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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
char N[100];
ll i, j, k;
int main(){
    scanf("%s", N);
    fornum(i,0,3){
        if(N[i]=='7'){
            break;
        }
    }
    if(i==3){
        printf("No\n");
    }else{
        printf("Yes\n");
    }
    return 0;
}

Measured memory_bytes: 3688
use std::io::*;
use std::str::FromStr;

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

fn main() {

    let n: usize = read();
    let mut vec: Vec<i64> = Vec::with_capacity(n);
    let mut v: Vec<i64> = Vec::with_capacity(n.clone());

    for _i in 0..n {
        vec.push(read())
    }

    for i in 0..n {
        let tmp = (vec[i] - (i+1) as i64);
        v.push(tmp);
    }
    v.sort();

    let mut mesian :i64 = 0;
    if v.len() % 2 != 0 {
        mesian = v[v.len() / 2];
    } else {
        mesian = (v[v.len() / 2 -1] + v[v.len() / 2]) / 2;
    }
    let ans = v.iter().fold(0, |sum, value| sum + (value - mesian).abs());
    println!("{}", ans);
}


Measured memory_bytes: 8444
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <sstream>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define SZ(x) (int)(x.size())
#define F0(i,n) for(int i=0;i<n;i++)
#define F1(i,n) for(int i=1;i<=n;i++)
#define CL(a,x) memset(x, a, sizeof(x));
const int MOD = 1000000007;
const double pi = atan(1.0)*4.0;
const double eps = 1e-8;
ll gcd(ll x, ll y) { return y ? gcd(y, x%y) : x; }
int bc(int n) { return n ? bc((n-1)&n)+1 : 0; }

int i, j, k, m, n, l, X, Y, Z, h, d[100005];
int a[100005], b[100005], c[100005];
ll ans, dist[100005], lo;
vector<int> cleans;
vector<int> goods;

vector<pii> adj[100005];

void dfs1(int i, int par = -1) {
    d[i] = 1;
    int good = 1;
    int clean = 1;
    for (pii p : adj[i]) if (p.first != par) {
        dfs1(p.first, i);
        d[i] += d[p.first];
        if (2 * d[p.first] > n) good = 0;
        if (2 * d[p.first] >= n) clean = 0;
    }
    int r = n - d[i];
    if (2 * r >= n) clean = 0;
    if (2 * r > n) good = 0;
    if (clean) cleans.push_back(i);
    if (good) goods.push_back(i);
}

void dfs2(int i, int par = -1) {
    ans += dist[i];
    if (cleans.empty()) {
        if (i == goods[1]) lo = min(lo, dist[i]);
    } else {
        if (par != -1) lo = min(lo, dist[i]);
    }
    for (pii p : adj[i]) if (p.first != par) {
        dist[p.first] = dist[i] + p.second;
        dfs2(p.first, i);
    }
}


int main() {

/*
    cin >> X >> Y >> Z;
    
    n = X + Y + Z;
    
    F0(i, n) {
        cin >> a[i] >> b[i] >> c[i];
        a[i] -= c[i];
        b[i] -= c[i];
        ans += c[i];
    }
*/

    cin >> n;
    F0(u,n-1) {
        cin >> i >> j >> k;
        adj[i].push_back(pii(j, k));
        adj[j].push_back(pii(i, k));
    }
    h = -1;    
    dfs1(1);
    
    //for (int x : goods) cout << x << " "; cout << " goods " << endl;
    //for (int x : cleans) cout << x << " "; cout << " cleans " << endl;
    
    h = cleans.empty() ? goods[0] : cleans[0];
    lo = 1e18;   
    dfs2(h);
    cout << 2 * ans - lo << endl;
    return 0;
}

Measured memory_bytes: 14592
#include<stdio.h>
long long d[10000001];
int main(){
	int n,i,h;
	for(i=0;i<=10000000;i++)d[i]=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&h);
		d[h-1]++;
	}
	long long ans=0;
	for(i=9999999;i>=0;i--){
		d[i]+=d[i+1];
		if(d[i]>4*(i+1))d[i]=4*(i+1);
		ans+=d[i];
	}
	printf("%lld\n",ans+1);
	return 0;
}

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

using ll=long long;
const int inf=100000000;

int in(){
  int a;
  cin >> a;
  return a;
}//int型関数の受け取り

void forin(int* x,int y){
  for (int i=0;i<y;i++){
    cin >> x[i];
  }
}//(x,y) int型配列x[y]の受け取り

int intpow(int x,int y){
  double a=x,b=y;
  return pow(a,b);
}//(x,y) xをy乗

int intfabs(int x){
  double a=x;
  return fabs(a);
}//(x) xの絶対値

int fact(int x){
  if (x == 1) return 1;
  return x*fact(x-1);
}//(x) x!

int fib(int x){
  if (x <= 2) return x;
  int a[x];
  a[0]=1;
  a[1]=2;
  for (int i=2;i<x;i++){
    a[i]=a[i-1]+a[i-2];
  }
  return a[x-1];
}//(x) フィボナッチ数列のx番目

int div1(ll x){
  return x%1000000007;
}

main(){
    int n=in(),l=in(),ans=0;
    for (int i=0;i<n;i++){
        ans+=l+i;
    }
    if (0<l) cout << ans-l << endl;
    else if (l+n-1<0) cout << ans-l-n+1 << endl;
    else cout << ans << endl;
}

Measured memory_bytes: 256
N, K =  map(int, input().split())

N_ = N
digits = 0
i = 0
while N_ / K >= K:
  digits += (10 ** i) * (N_ % K)
  N_ = int(N_ / K)
  i += 1

N_ = int(N_ / K)
digits += (10 ** (i + 1)) * (N_ % K)

print(len(str(digits)))

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = 99999999;
const ll linf = 999999999999999999;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.end(), v.begin());
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - a) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
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; }

///////////////////////////////////////////////////////////////////////////

int main(){
	ll x;
	cin >> x;
	ll ans = 0;

    if(x >= 11){
        ans += (x/11)*2;
        x %= 11;
    }
	int i = 0;
	while(x > 0){
//	P(x);
        if(i%2 == 0){
            x -= 6;
            ans++;
        }else{
            x -= 5;
            ans++;
        }
        i++;
	}
	P(ans);
	return  0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
using P = pair<ll, ll>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i, n) for(ll i=1;i<=(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define INF 1000000000

#define EVEN	0
#define ODD		1

ll a[502][502];

void solve_abc108_c() {
	ll N, K;
	ll ans = 0;

	cin >> N >> K;

	if (K % 2 == 1) {
		ans = pow(N / K, 3);
	}
	else {
		if (N % K >= K / 2) {
			ans = pow(N / K, 3) + pow(N / K + 1, 3);
		}
		else {
			ans = pow(N / K, 3) + pow(N / K, 3);
		}
	}

	cout << ans << "\n";
}


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

	solve_abc108_c();

	return 0;
}


Measured memory_bytes: 256
N, Q = map(int, input().split())
S = input()
s = [0]*N
A = []
for n in range(N-1):
    if S[n] + S[n+1] == 'AC':
        s[n+1] = s[n] + 1
    else:
        s[n+1] = s[n]
for q in range(Q):
    l, r = map(int, input().split())
    A.append(s[r-1] - s[l-1])
for a in A:
    print(a)

Measured memory_bytes: 10308
/*
貪欲
後ろから見る
DP
順位表をチェック
二分探索
不変なもの・偶奇に注目

*/
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include <cmath>
#include <limits>
#include <iostream>
#include <map>
#include<tuple>
#include<set>
using namespace std;
#define INF 1LL<<60
#define MAX 100000
#define MOD 1000000007
typedef long long ll;
typedef pair<int,int> P;
//typedef pair< pair<int,int>,pair<int,int> > p;
//#define int ll int main->signed main
#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)
struct edge{ll to,cost,val;};
template<class T,class U>bool chmin(T&a,const U&b){if(a<=b)return false;a=b;return true;}
template<class T,class U>bool chmax(T&a,const U&b){if(a>=b)return false;a=b;return true;}
//__builtin_popcount(S);
//C.erase(unique(C.begin(),C.end()),C.end());

//http://drken1215.hatenablog.com/entry/2018/09/30/004816

int main(){
    string S;
    cin>>S;
    if(S[0]=='0' || S.back()=='1'){
        cout<<-1<<endl;
        return 0;
    }
    int N=(int)S.size();
    bool ok=true;
    for(int i=1;i<N;i++){
        int j=N-i;
        if(S[i-1]!=S[j-1]) ok=false;
    }
    if(!ok){
        cout<<-1<<endl;
        return 0;
    }
    int pre=N;
    for(int i=N-1;i>=1;i--){
        cout<<i<<" "<<pre<<endl;
        if(S[i-1]=='1') pre=i;
    }
}


Measured memory_bytes: 1600
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<math.h>
#include<string>
#include <iomanip>
#include<deque>

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;
const ll LINF = 1e18;
const int INF = 1e8;

using namespace std;


//マクロ定義
#define vvint(vec,n,m,l) vector<vector<int>> vec(n, vector<int>(m,l));	// lで初期化
#define vvll(vec,n,m,l) vector<vector<ll>> vec(n,vector<ll>(m,l));
#define vint vector<int>
#define pint pair<int,int>
#define rep(i,a) for(int i=0;i<(a);i++)
#define all(x) (x).begin(),(x).end()
#define debug system("pause")				//デバッグ用


int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int n, d;
	cin >> n >> d;

	cout << (n + (1+2*d) - 1) / (1 + 2 * d) << endl;


}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(v) v.begin(), v.end()
using ll = long long;
const int inf = int(1e10);
const int mod = int(1e9) + 7;


using Graph = vector<vector<int>>;
int n, m, res = 0;
Graph G(30);

void dfs(vector<bool> &seen, int v, int cnt){
    if(cnt == n - 1){
        res++;
        return;
    }
    seen[v] = true;
    for(auto next_v: G[v]){
        if(seen[next_v]) continue;
        dfs(seen, next_v, cnt + 1);
    }
    
    seen[v] = false;
}

int main(){
    cin >> n >> m;
    vector<bool> seen;
    seen.assign(n, false);

    rep(i, m){
        int a, b;
        cin >> a >> b;
        G[a - 1].push_back(b - 1);
        G[b - 1].push_back(a - 1);
    }
    dfs(seen, 0, 0);
    cout << res << endl;

}

Measured memory_bytes: 3632
MOD = 10 ** 9 + 7

X, Y = map(int, input().split())

a, b = (2 * X - Y) // 3, (2 * Y - X) // 3
maxf = a + b + 10

if (not ((2 * X - Y) % 3 == 0 and (2 * Y - X) % 3 == 0)) or (a < 0 or b < 0):
    print(0)
    exit()

f, invf = [1] * maxf, [1] * maxf

for i in range(1, maxf):
    f[i] = (f[i - 1] * i) % MOD
invf[maxf - 1] = pow(f[maxf - 1], MOD - 2, MOD)
for i in range(maxf - 1, 0, -1):
    invf[i - 1] = (invf[i] * i) % MOD

comb = lambda a, b: f[a + b] * invf[a] * invf[b] % MOD

print(comb(a, b) % MOD)


Measured memory_bytes: 55796
#include <iostream>
#include <string>
#include <algorithm>

#define LEN 100000
using namespace std;

class Pro{
public:
	string name;
	int time;
};

class Que{
	Pro* p = new Pro[LEN];
public:
	~Que(){ delete[] p; }
	int head=0, tail=0, n;
	void enqueue(Pro x){
		p[tail] = x;
		tail = (tail + 1) % LEN;
	}

	Pro dequeue(){
		Pro x = p[head];
		head = (head + 1) % LEN;
		return x;
	}
};


int main()
{
	int n;//??????????????°
	cin >> n;
	int q;//?????????????????????
	cin >> q;
	
	Que Q;
	for (int i = 0; i < n; i++){
		Pro x;
		cin >> x.name;
		cin >> x.time;
		Q.enqueue(x);
	}

	//????????????
	int t=0;

	while (Q.head != Q.tail){
		Pro c;
		c = Q.dequeue();
		int b = min(c.time, q);
		c.time -= b;
		t += b;

		if (c.time > 0) {
			Q.enqueue(c);
		}
		else{
		cout << c.name << ' ' << t << '\n';
		}
	}
	return 0;
}

Measured memory_bytes: 6712
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		char s = sc.next().charAt(0);
		
		if(Character.isUpperCase(s)) {
			System.out.println("A");
		}else {
			System.out.println("a");
		}
		
	}

}


Measured memory_bytes: 35636
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ff              first
#define fo(i,n)         for(i=0;i<n;i++)
#define Fo(i,k,n)       for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define deb(x)          cout << #x << "=" << x << endl
#define deb2(x, y)      cout << #x << "=" << x << "," << #y << "=" << y << endl
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define w(x)            int x; cin>>x; while(x--)
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const int N = 3e5, M = N;
//=======================

vi g[N];

void solve() {
	int i, j, n, m;
	int k;
	cin >> n >> k;
	int a[n];
	fo(i, n) cin >> a[i];
	int dp[n + 1][k + 1];
	//dp[studenet][candies]
	fo(i, k + 1) {
		dp[0][i] = 0;
	}
	fo(j, n + 1) {
		dp[j][0] = 1;
	}
	std::vector<int> prefix(k + 1);
	Fo(i, 1, n + 1) {
		Fo(j, 0, k + 1) {
			prefix[j] = dp[i - 1][j] % mod;
			if (j) prefix[j] = (prefix[j] % mod + prefix[j - 1] % mod) % mod;
		}
		Fo(j, 1, k + 1) {
			if (j <= a[i - 1]) {
				dp[i][j] = prefix[j] % mod;
			}
			else {
				int non_cnting = j - a[i - 1] - 1;
				dp[i][j] = ( prefix[j] % mod - prefix[non_cnting] % mod + mod) % mod;
			}
		}
		prefix.clear();
	}
	cout << dp[n][k];
}

int32_t main()
{
	FIO;
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	solve();
	return 0;
}



Measured memory_bytes: 89980
#include <iostream>
#include <algorithm>
#include <string> 
#include <vector>
#include <iomanip>
#include <math.h>
using namespace std;

int main()
{
	string s;
	cin >> s;
	int N = 0; int W = 0;
	int S = 0; int E = 0;
	bool NS = false; bool WE = false;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'N') {
			N++;
		}
		else if (s[i] == 'W') {
			W++;
		}
		else if (s[i] == 'S') {
			S++;
		}
		else if (s[i] == 'E') {
			E++;
		}
	}
	if ((W == 0 && E == 0) || (W != 0 && E != 0)) {
		WE = true;
	}
	if ((N == 0 && S == 0) || (N != 0 && S != 0)) {
		NS = true;
	}
	if (NS && WE) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 256
import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)

def main():
    S = input()
    if S[0] == "S":
        print("Cloudy")
    elif S[0] == "C":
        print("Rainy")
    else:
        print("Sunny")


if __name__ == '__main__':
    main()

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

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;

const long long INF = 1LL << 60;

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

int main()
{
    ll N, M;
    cin >> N >> M;

    ll A[M], B[M];
    rep(i, M) {
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
    }

    UnionFind tree(N);

    ll ans[M];
    ans[0] = (N * (N - 1)) / 2;

    repd(i, 1, M) {
        if (tree.issame(A[M - i], B[M - i])) {
            ans[i] = ans[i - 1];
        }
        else {
            ll a = tree.size(A[M - i]);
            ll b = tree.size(B[M - i]);
            ans[i] = ans[i - 1] - a * b;
            tree.merge(A[M - i], B[M - i]);
        }
    }

    for (int i = M - 1; i >= 0; i--) {
        cout << ans[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 4096
#include<stdio.h>
#include<string.h>
int C[6],F[6][6][6][6][6];
void rotate(a,b,c,d){
	int t;
	t=C[a];
	C[a]=C[b];
	C[b]=C[c];
	C[c]=C[d];
	C[d]=t;
}
void normalize(){
	int i,m;
	while(C[1]==0||C[4]==0)
		rotate(1,2,4,3);
	while(C[0]!=0)
		rotate(0,2,5,3);
	m=1;
	for(i=2;i<=4;i++)
		if(C[i]<C[m])
			m=i;
	m=C[m];
	while(C[1]!=m)
		rotate(1,2,4,3);
}
int main(){
	int n,i,*p,remain;
	char str[10];
	char*table="RYBMGC";
	for(;scanf("%d",&n),n;){
		memset(F,0,sizeof(F));
		remain=n;
		for(;n--;){
			for(i=0;i<6;i++){
				scanf("%s",str);
				C[i]=strchr(table,str[0])-table;
			}
			normalize();
			p=&F[C[1]][C[2]][C[3]][C[4]][C[5]];
			if(*p==0){
				remain--;
				*p=1;
			}
		}
		printf("%d\n",remain);
	}
	exit(0);
}

Measured memory_bytes: 0
import sys
from collections import deque, defaultdict, Counter
from itertools import accumulate, product, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush
from math import ceil, floor, sqrt, gcd, inf
from copy import deepcopy
import numpy as np
import scipy as sp

INF = inf
MOD = 1000000007

x, n = [int(i) for i in input().split()]
P = [int(i) for i in input().split()]

tmp = 0
res = 0

P = np.array(P) - x

while True:
    if not -res in P:
        res *= -1
        break
    if not res in P:
        break
    res += 1
res += x

print(res)


Measured memory_bytes: 31200
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Main{
	static BufferedReader br;
	static int cin() throws Exception
	{
		return Integer.valueOf(br.readLine().replaceAll("\\s", ""));
	}
	static int[] split() throws Exception
	{
		String[] cmd=br.readLine().split(" ");
		int[] ans=new int[cmd.length];
		for(int i=0;i<cmd.length;i++)
		{
			ans[i]=Integer.valueOf(cmd[i]);
		}                                              
		return ans;
	} 
	static long[] splitL() throws IOException
	{
		String[] cmd=br.readLine().split(" ");
		long[] ans=new long[cmd.length];
		for(int i=0;i<cmd.length;i++)
		{
			ans[i]=Long.valueOf(cmd[i]);
		}
		return ans;
	}
	static long mod=1000000007;
	static long power(long x,long y) 
    { 
        long res = 1; 
        x = x % mod; 
        while (y > 0) { 
            if (y % 2 == 1) 
                res = (res * x) % mod; 
            y = y >> 1;
            x = (x * x) % mod; 
        } 
        return res%mod; 
    } 
    static long modInverse(long n) 
    { 
        return power(n, mod-2); 
    } 
    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        long[]ar=splitL();
        long x=Math.abs(ar[0]);
        long k=ar[1];
        long d=ar[2];
        long y=(x/d)+1;
        if(y>k)
        {
        	System.out.println(Math.abs(x-k*d));
        }
        else
        {
        	long rem=k-y;
        	x=x-y*d;
        	long s=rem%2;
        	System.out.println(Math.abs(x+s*d));
        }
    }
}

Measured memory_bytes: 32620
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<((int)n); i++)
#define REP(i,n) for(int i=0; i<=((int)n); i++)
#define srep(i,a,n) for(int i=a; i<((int)n); i++)
#define SREP(i,a,n) for(int i=a; i<=((int)n); i++)
#define rrep(i,n) for(int i=n-1; i>=0; i--)
#define RREP(i,n) for(int i=n; i>=0; i--)
#define INF 1000000000
#define ALL(v) (v).begin(), (v).end()
const int mod = INF+7;
using namespace std;

int factorial(int n){
  int pro=1;
  srep(i,1,n+1){
    pro=(long)pro*i%mod;
  }
  return pro;
}

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

  int *lr=(int *)malloc(sizeof(int)*N*2);
  //left:0, right:1
  if(S[0]=='W' || S[2*N-1]=='W'){
    printf("%d\n", 0);
  }
  else{
    lr[0]=0;
    srep(i,1,N*2){
      if(S[i-1]==S[i]){
        if(lr[i-1]==0){
          lr[i]=1;
        }
        else{
          lr[i]=0;
        }
      }
      else{
        if(lr[i-1]==0){
          lr[i]=0;
        }
        else{
          lr[i]=1;
        }
      }
    }
    int count=0;
    int sum=1;
    rrep(i,N*2){
      if(lr[i]==1){
        count++;
      }
      else if(lr[i]==0){
        sum=(long)sum*count%mod;
        count--;
      }
    }
    if(count!=0){
      printf("%d\n", 0);
    }
    else{
      sum=(long)sum*factorial(N)%mod;
      printf("%d\n", sum);
    }
  }


}


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



int main() {
  ll l,r;
  cin >> l >> r;
  int ans=114514;
  FOR(l,r){
      for(ll j=l;j<r+1;j++){
          if(j==i){
              continue;
          }
          if((j*i)%2019==0){
              cout << 0 << endl;
              return 0;
          }
          if(ans>(j*i)%2019){
              ans=(j*i)%2019;
          }
      }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
n, a, b = STDIN.gets.chomp.split.map{|s| s.to_i }

total = 0
(1..n).each do |i|
  str_i   = i.to_s
  i_10000 = str_i[-5].to_i
  i_1000  = str_i[-4].to_i
  i_100   = str_i[-3].to_i
  i_10    = str_i[-2].to_i
  i_1     = str_i[-1].to_i
  sum = i_10000 + i_1000 + i_100 + i_10 + i_1
  if (a <= sum) && (sum <= b)
    total += i
  end
end

puts total

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

int main(void){
    // Your code here!
    int l;
    double l_f;
    scanf("%d", &l);
    
    l_f=(double)l/3.0;
    printf("%lf", l_f*l_f*l_f);
}


Measured memory_bytes: 128
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
#define vec(s) vector

#define vvec(s) vector<vector
>
typedef vector<lli> vi;
typedef vector<vi> vvi;
typedef pair<lli,lli> pii;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Yes(x) cout<<(x?"Yes":"No")<<endl;
#define YES(x) cout<<(x?"YES":"NO")<<endl;
#define out(s) cout<<s<<endl;
#define pb(s) push_back(s);
#define sp " " 
#define INF 10000000000
#define LINF 9000000000000000000
#define all(s) s.begin(),s.end()
void vout(vi v){
    for(lli i=0;i<v.size();i++)
    cout<<v.at(i)<<endl;
}
int main(){
    cout << std::fixed << std::setprecision(10);
    lli a, b;
    cin>>a>>b;
    if(a>9||b>9){ 
        out(-1);
    }
    else{ 
        out(a*b);
    }
}

Measured memory_bytes: 3676
#include <bits/stdc++.h>
using namespace std;
int main(){
	char s[18];
	for(int i=0;i<19;i++){
		cin>>s[i];
		if(s[i]==',')s[i]=' ';
	}
	for(int j=0;j<19;j++)cout<<s[j];
	cout<< endl;
}

Measured memory_bytes: 256