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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define PI 3.14159265358979
#define MOD 1000000007 // = 10^9 + 7

using namespace std;
using ll = long long;


void solve()
{
	int n;
	cin >> n;

	int a;
	bool ans = true;
	for(int i = 0; i < n; ++i)
	{
		cin >> a;
		ans = ans & ((a & 1) | (a % 3 == 0) | (a % 5 == 0));
	}

	cout << (ans ? "APPROVED" : "DENIED");

}

int main()
{
	fastio;
	solve();

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  string S;
  cin >> S;
    
  int slen=(int)S.length();
  
  while(1){
    S.erase((int)S.length()-1);
    //cout<<S<<endl;
    string last = S.substr((int)S.length()/2);
    string front = S.substr(0,S.length()/2);
     
    //cout<<front<<" "<<last<<endl;
    if(S.substr((int)S.length()/2)==S.substr(0,S.length()/2)){
      cout<<S.length()<<endl;
      return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 256
a=[int(input())]
for i in range(1000000):
    n=a[i]
    if n%2==0:
        a.append(int(n/2))
    else:
        a.append(3*n+1)

for i in range(1000000):
    if a[i-3]==a[i]:
        print(i+1)
        break

Measured memory_bytes: 10900
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <climits>

using namespace std;

//BEGIN
template <typename T>
struct SegmentTree {
        using F = function<T(T, T)>;
        
        int n;
        vector<T> tree;
        const F f;
        const T ti;

        SegmentTree() {}
        SegmentTree(F f, T ti) :f(f), ti(ti) {}

        void init(int n_) {
                n = 1;
                while (n < n_) n *= 2;
                tree.assign(2 * n, ti);
        }

        void build(const vector<T>& v) {
                int n_ = v.size();
                init(n_);
                for (int i = 0; i < n_; ++i) tree[n + i] = v[i];
                for (int i = n - 1; i > 0; --i) tree[i] = f(tree[2 * i], tree[2 * i + 1]);
        }

        void update(int i, const T& x) {
                i += n;
                tree[i] = x;
                while (i >>= 1) tree[i] = f(tree[2 * i], tree[2 * i + 1]);
        }

        T find(int l, int r) { // [l, r)
                l += n, r += n;
                T ll = ti, rr = ti;
                while (l < r) {
                        if (l & 1) ll = f(ll, tree[l++]);
                        if (r & 1) rr = f(rr, tree[--r]);
                        l >>= 1, r >>= 1;
                }
                return f(ll, rr);
        }

        T at(int i) { return tree[i + n]; }
};
//END

void DSL_2_A() {
        int n, q; cin >> n >> q;
        SegmentTree<int> seg([](int a, int b) { return min(a, b); }, INT_MAX);
        seg.init(n);
        while (q--) {
                int com, x, y; cin >> com >> x >> y;
                if (com) cout << seg.find(x, y + 1) << endl;
                else seg.update(x, y);
        }
}
/*
        created: 2019-11-30
        https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_A
*/

int main() {
        DSL_2_A();

        return 0;
}


Measured memory_bytes: 3904
import java.io.*;
public class Main{
	public static void main(String[] args)throws Exception{
		BufferedReader input=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		String str=input.readLine();
		int n=Integer.parseInt(str);
		int ii=0;
		for(int i=0;i<=n;i++){
			if(!(i==0)){
				if(i%3==0){
					sb.append(" ").append(i);
					}else{
						 ii=i;
						while(!(ii==0)){
							if(ii%10==3){
								sb.append(" ").append(i);
								break;
							}
							ii/=10;
						}
					}
				}		
			}	
		
		System.out.println(sb);
	}
}

Measured memory_bytes: 25184
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long int n,m,sum=0,i,a;
	cin>>n>>m;
	for(i=1;i<=m;i++)
	{
		cin>>a;
		sum+=a;
	}
	if(n-sum>=0)
	cout<<n-sum<<endl;
	else
	cout<<"-1"<<endl;
	
	
	
	
	
	
	return 0;
}

Measured memory_bytes: 3636
N = input()
K = int(input())
N = "0" + N
K = int(K)

L = len(N)

dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(L)]
dp[0][0][0] = 1

for i in range(1, L):
    d = int(N[i])
    # 境界
    for k in range(0, K + 1):
        dp[i][1][k] += dp[i - 1][1][k]
        if d != 0:
            dp[i][1][k] += dp[i - 1][0][k]

    for k in range(1, K + 1):
        dp[i][1][k] += dp[i - 1][1][k - 1] * 9
        if d != 0:
            dp[i][1][k] += dp[i - 1][0][k - 1] * (d - 1)
            dp[i][0][k] += dp[i - 1][0][k - 1]
        else:
            dp[i][0][k] += dp[i - 1][0][k]

print(dp[-1][0][K] + dp[-1][1][K])


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

#define optimizar_io ios_base::sync_with_stdio(0);cin.tie(0);

using namespace std;

int main(){
	optimizar_io;
	int N;
	string str;
	cin >> N >> str;
	int changes = 1;
	for (int i = 1; i < str.size(); i++){
		if (str[i] != str[i-1]) changes++;
	}
	cout << changes << endl;
	return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define re register
#define int long long
using namespace std;

inline int read(){
	re int ans = 0;re bool f = 1;re char ch = getchar();
	while(ch<'0'||ch>'9'){if (ch=='-')f = 0;ch = getchar();}
	while(ch>='0'&&ch<='9'){
		ans = (ans<<3)+(ans<<1)+(ch^48);
		ch = getchar();
	}
	return f?ans:~(ans-1);
}
int a[204800],b[204800];

signed main(void){
	int n,m,k,ans = 0;
	n = read(),m = read(), k = read();
	for(re int i=1;i<=n;++i)
		a[i] = a[i-1]+read();
	for(re int i=1;i<=m;++i)
		b[i] = b[i-1]+read();
	int j = m;
	for(re int i=0;i<=n&&a[i]<=k;++i){
		while(j>=0&&a[i]+b[j]>k)j--;
		ans = max(ans,i+j);
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 6804
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define mrep(i,j,n) for(int i = j; i < n; i++)
#define reps(i,n) for(int i = 1; i <= n; i++)
#define rrep(i,n) for(int i = n-1; i >= 0; i--)
#define mreps(i,j,n) for(int i = j; i <= n; i++)
#define rreps(i,n) for(int i = n; i >= 1; i--)
#define co(x) cout << x <<endl
#define cs(x) cout << x <<" "
#define el cout << endl
#define sp(x) cout << setprecision(x);
#define cer(x) cerr << x <<endl
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(ALL(x), val), x.end())
#define vi vector<int> 
#define vvi vector<vector<int>> 
#define vpii vector<pair<int,int>> 
#define vl vector<ll> 
#define vvl vector<vector<ll>> 
#define vd vector<double> 
#define vvd vector<vector<double>> 
#define vb vector<bool> 
#define vvb vector<vector<bool>>
#define vs vector<string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll mod = 1e9 + 7;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a * b / g; }
bool is_prime(ll x) { for (ll i = 2; i * i <= x; i++) { if (x % i == 0)return false; } return true; }


int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, k; cin >> n >> k;
	vl h(n);
	rep(i, n)cin >> h[i];
	sort(all(h));
	reverse(all(h));
	ll ans = 0;
	mrep(i, k, n)
	{
		ans += h[i];
	}
	co(ans);
	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define em emplace
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, n) for(int i = 1; i <= n; i++)
template<class T> inline int chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline int chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
constexpr int INF = 1<<30;
constexpr ll LINF = 1LL<<58;
constexpr int mod = 1000000007;

int dp[100010][3];
int X[100010][3];

int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> X[i][0] >> X[i][1] >> X[i][2];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                if(j == k) continue;
                chmax(dp[i + 1][j], dp[i][k] + X[i][j]);
            }
        }
    }
    cout << max(dp[n][0], max(dp[n][1], dp[n][2])) << endl;
    return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef pair<ll, int> li;
typedef pair<int, ll> il;
typedef pair<ll , ll> lli;
typedef vector<ii> vii;
typedef vector<il> vil;
typedef vector<li> vli;
typedef vector<lli> vlli;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define in insert
#define f0(b) for(int i=0;i<(b);i++)
#define f00(b) for(int j=0;j<(b);j++)
#define f1(b) for(int i=1;i<=(b);i++)
#define f11(b) for(int j=1;j<=(b);j++)
#define f2(a,b) for(int i=(a);i<=(b);i++)
#define f22(a,b) for(int j=(a);j<=(b);j++)
#define sf(a) scanf("%lld",&a)
#define sff(a,b) scanf("%lld %lld", &a , &b)
#define pf(a) printf("%lld\n",a)
#define pff(a,b) printf("%lld %lld\n", a , b)
#define PI 3.14159265359
#define bug printf("**!\n")
#define mem(a , b) memset(a, b ,sizeof(a))
#define front_zero(n) __builtin_clzll(n)
#define back_zero(n) __builtin_ctzll(n)
#define total_one(n) __builtin_popcountll(n)

const ll mod = (ll)1e9+7;
const ll maxn = (ll)2e5+5;
const int nnn = 1048590;
const int inf = numeric_limits<int>::max()-1;
//const ll INF = numeric_limits<ll>::max()-1;
const ll INF = 1e18;

ll dx[]={0,1,0,-1};
ll dy[]={1,0,-1,0};
ll dxx[]={0,1,0,-1,1,1,-1,-1};
ll dyy[]={1,0,-1,0,1,-1,1,-1};

void solve(){
	ll a[maxn];
	mem(a, 0);
	ll b;
	ll n,q,sum = 0;
	cin >> n;
	f0(n) cin >> b, a[b]++ , sum += b;
	cin >> q;
	while(q--){
		ll x,y;
		cin >> x >> y;
		ll k = a[x];
		ll diff = y-x;
		sum += diff*k;
		a[x] = 0;
		a[y] += k;
		cout << sum << '\n';
	} 
	return;
}


int main() {
   
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    ll T;
    T=1;
    //cin >> T;
    //scanf("%lld",&T);
    ll CT = 0;
    //work();
    while(T--){
    	//cout << "Case " << ++CT <<": " ;
    	//printf("Case %lld: ",++CT);
		solve();
	}
    
    return 0;
}


Measured memory_bytes: 5224
#  --*-coding:utf-8-*--

def f(S, T):
    lastIndex = None
    pat = None

    for i in range(len(S)-len(T)+1):
        pat2 = g(S, T, i)

        if pat2 != None and (pat == None or pat2 < pat):
            pat = pat2

    if pat == None:
        return 'UNRESTORABLE'

    S2 = list(S)
    for index, letter in pat:
        S2[-index] = letter

    return ''.join(S2).replace('?', 'a')
            


def g(S, T, st):
    pat = []

    for i in range(len(T)):
        s = S[st + i]
        t = T[i]

        if s == '?':
            if t != 'a':
                pat.append((-(st + i), t))
        elif s != t:
            return None

    return pat
        

def test():
    assert f('?tc????', 'coder') == 'atcoder'
    assert f('??p??d??', 'abc') == 'UNRESTORABLE'


def main():
    S = input()
    T = input()
    print(f(S, T))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3188
// Copyright 2019 yaito3014
#include "bits/stdc++.h"
using namespace std;
using namespace literals;

struct Edge {
  int to, cost;
  Edge() = default;
  Edge(int t, int c)
    : to(t), cost(c) {}
};

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  vector<vector<Edge>> G(N);
  for (int i = 0; i < N - 1; ++i)
    G[i + 1].push_back(Edge(i, 0));  // N→1にはノーコストで動ける
  for (int i = 0; i < M; ++i) {
    int L, R, C;
    cin >> L >> R >> C;
    G[--L].push_back(Edge(--R, C));  // C使ってL→Rに行ける
  }
  vector<int64_t> cost(N, INT64_MAX);
  cost[0] = 0;
  using P = pair<int64_t, int>;  // first: cost, second: index
  priority_queue<P, vector<P>, greater<P>> que;
  que.push(P(0, 0));
  while (!que.empty()) {
    P cur = que.top(); que.pop();
    for (Edge& nxt : G[cur.second]) {
      int64_t c = cur.first + nxt.cost;
      if (cost[nxt.to] <= c)continue;
      cost[nxt.to] = c;
      que.push(P(c, nxt.to));
    }
  }
  int64_t ans = cost[N - 1];
  if (ans == INT64_MAX)ans = -1;
  cout << ans << endl;
}


Measured memory_bytes: 8440
#include <stdio.h>
int main(void){

int m,f,r;

while(1){
    scanf("%d %d %d\n",&m,&f,&r);
    if (m == -1 && f == -1 && r == -1) break;
    if (m == -1 || f == -1 || m+f < 30){
        printf("F\n");
        continue;
    }
    if (m+f >= 80){
        printf("A\n");
        continue;
    }
    if (m+f >= 65){
        printf("B\n");
        continue;
    }
    if (m+f >= 50 || r >= 50){
        printf("C\n");
        continue;
    }
    if (m+f >= 30){
        printf("D\n");
        continue;
    }
}

return 0;
}



Measured memory_bytes: 2044
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <string>
#include <algorithm>
#include <string>
#include <climits>

#define REP(i, n) for (int (i) = 0; (i) < (int)(n); (i)++)
#define REG(i, a, b) for (int (i) = ((int)(a)); (i) < ((int)(b)); i++)
#define ALL(V) (V).begin(), (V).end()
#define PRINT(STR) cout << (STR) << endl

typedef long long ll;
using namespace std;
const int INF = 999999;

int main() {
	cin.tie(0); //?????±?????????????????????
	ios::sync_with_stdio(false); //printf??¨??±??????????????????
	int n, m;
	int Taros[101];
	int Hanakos[101];
	while (cin >> n >> m, n + m != 0) {
		fill(Taros, Taros + 101, 0);
		fill(Hanakos, Hanakos + 101, 0);
		int sum1 = 0, sum2 = 0;
		REP(i, n) {
			cin >> Taros[i];
			sum1 += Taros[i];
		}
		REP(i, m) {
			cin >> Hanakos[i];
			sum2 += Hanakos[i];
		}
		int sum_min = INF, a, b;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (sum1 - Taros[i] + Hanakos[j] ==
						sum2 - Hanakos[j] + Taros[i]) {
					if (sum_min > Taros[i] + Hanakos[j]) {
						a = Taros[i];
						b = Hanakos[j];
						sum_min = a + b;
					}
				}
			}
		}
		if (sum_min == INF) {
			cout << -1 << endl;
		} else {
			cout << a << " " << b << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 1196
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>
#include <numeric>

using namespace std;

#define mod 1000000007
long long int result[2000][2000] = {};

int main()
{
	int n, m;
	cin >> n >> m;
	int s[2000], t[2000];
	for (int i = 0; i < n; i++)
	{
		cin >> s[i];
	}
	for (int j = 0; j < m; j++)
	{
		cin >> t[j];
	}
	result[0][0] = 1;
	if (s[0] == t[0])
		result[0][0]++;
	for (int j = 1; j < m; j++)
	{
		result[0][j] = result[0][j - 1];
		if (s[0] == t[j])
			result[0][j]++;
		result[0][j] %= mod;
	}
	for (int i = 1; i < n; i++)
	{
		result[i][0] = result[i - 1][0];
		if (s[i] == t[0])
			result[i][0]++;
		result[i][0] %= mod;
		for (int j = 1; j < m; j++)
		{
			result[i][j] = result[i - 1][j] + result[i][j - 1] - result[i - 1][j - 1];
			if (s[i] == t[j])
				result[i][j] += result[i - 1][j - 1];
			result[i][j] += mod;
			result[i][j] %= mod;
		}
	}
	cout << result[n - 1][m - 1] << endl;
}

Measured memory_bytes: 31488
#include <bits/stdc++.h>
using namespace std;main(){int n,x,a[101],ans=0;cin>>n>>x;for(int i=0;i<n;i++){cin>>a[i];}sort(a,a+n);for(int i=0;i<n-1;i++){if(a[i]>x)break;x-=a[i];ans++;}cout<<(x-a[n-1]?ans:ans+1);}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
diff = [0 for _ in range(N)]
for i in range(N):
    diff[i] = A[i] - B[i]
diff = sorted(diff)
diff_copy = diff.copy()

i = 0
j = N-1

flag = True
while True:
    if diff[i]<0:
        while True:
            if i>=N or j<0 or i==j:
                flag = False
                break

            if abs(diff[i])>diff[j]:
                diff[i] += diff[j]
                diff[j] = 0
                j -= 1
            else:
                diff[j]-=abs(diff[i])
                diff[i] = 0
                break
        i += 1
    else:
        break



if flag:
    ans = 0
    for i in range(N):
        if diff_copy[i]!=diff[i]:
            ans += 1
    print(ans)
else:
    print(-1)


Measured memory_bytes: 19068
#import <Foundation/Foundation.h>

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        NSData *stdinData = [[NSFileHandle fileHandleWithStandardInput] availableData];
        NSString *s = [[NSString alloc] initWithData:stdinData encoding:NSUTF8StringEncoding];
        NSMutableString *answer = [NSMutableString stringWithString:s];
        [answer replaceCharactersInRange:NSMakeRange(5,1) withString:@" "];
        [answer replaceCharactersInRange:NSMakeRange(13,1) withString:@" "];
        
        NSFileHandle *fileHandle = [NSFileHandle fileHandleWithStandardOutput];
        [fileHandle writeData:[answer dataUsingEncoding:NSUTF8StringEncoding]];
        [fileHandle writeData:[@"\n" dataUsingEncoding:NSUTF8StringEncoding]];
        [fileHandle closeFile];
    }
    
    return 0;
}


Measured memory_bytes: 2404
#include <iostream>
#include<string>

using namespace std;

int main()
{
    string s;
    cin>>s;
    if(s=="Sunny"){
        cout<<"Cloudy";}
    if(s=="Cloudy"){
        cout<<"Rainy";}
    if(s=="Rainy"){
        cout<<"Sunny";}
    return 0;
}


Measured memory_bytes: 256
program kadai
integer  ::  N,M,i
integer,allocatable  ::  a(:)
integer  ::  ans
integer,allocatable  ::  s(:),c(:)


read(*,*) N,M
allocate(s(M))
allocate(c(M))
allocate(a(N))
do i=1,M
    read(*,*) s(i),c(i)
end do

a=10
do i=1,M
    if (a(s(i))==10) then
        a(s(i))=c(i)
    else if (a(s(i))/=c(i)) then
        write(*,*) -1
        stop
    end if
end do

if (N>1 .and. a(1)==0) then
    write(*,*) -1
    stop
end if

if (N>1 .and. a(1)==10) then
    a(1)=1
end if
if (N==1 .and. a(1)==10) then
    a(1)=0
end if
if (N>1) then
    do i=2,N
        if (a(i)==10) then
            a(i)=0
        end if
    end do
end if

ans=0
!#write(*,*) a
do i=1,N
    ans=ans+a(i)*(10**(N-i))
end do
write(*,*) ans


stop



end program kadai


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>
#include <bitset>

//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 998244353;
const long long INF = 1e18;
typedef long long LL;
typedef long double LD;
typedef pair<LL, LL> PLL;
typedef pair<LD, LL> pdl;
typedef pair<LD, LD> pdd;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef unsigned long long ULL;
//typedef boost::multiprecision::cpp_int bigint;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	LL N;
	cin >> N;
	string S;
	cin >> S;
	VLL M(2 * N + 1, 0), C(2 * N + 1,0);
	VLL Ds;
	for (LL n = 0; n < N; n++) {
		if (S[n] == 'D')Ds.push_back(n + 1);
		if (S[n] == 'M')M[n + 1]++;
		if (S[n] == 'C')C[n + 1]++;
		M[n + 1] += M[n];
		C[n + 1] += C[n];
	}
	for (LL n = N + 1; n <= 2 * N; n++) {
		M[n] = M[n - 1];
		C[n] = C[n - 1];
	}
	VLL DP(2 * N + 1, 0);
	for (LL n = N; n >= 1; n--) {
		DP[n] = DP[n + 1];
		if (S[n - 1] == 'M')DP[n] += C.back() - C[n];
	}
	LL Q;
	cin >> Q;
	for (LL q = 0; q < Q; q++) {
		LL K;
		cin >> K;
		LL ans = 0;
		for (LL d : Ds) {
			LL temp = DP[d + 1] - DP[d + K] - (M[d + K - 1] - M[d]) * (C.back() - C[d + K-1]);
			ans += temp;
		}
		cout << ans << "\n";
	}
	return 0;
}


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

int main(){
	int n;
	cin >> n;
  	vector<int> a(n);
  	for(int i = 0; i< n;i++)
      cin >> a[i];
  	sort(a.begin(),a.end());
  	cout << a[n-1] - a[0] << endl;
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		
		String s = sc.next();
		if(s.charAt(s.length() - 1) == 's')
			pw.println(s + "es");
		else
			pw.println(s + "s");
		
		pw.flush();
	}

	public static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public int[] nextIntArray(int n) throws IOException {
			int[] array = new int[n];
			for (int i = 0; i < n; i++)
				array[i] = nextInt();
			return array;
		}

		public Integer[] nextIntegerArray(int n) throws IOException {
			Integer[] array = new Integer[n];
			for (int i = 0; i < n; i++)
				array[i] = new Integer(nextInt());
			return array;
		}

		public long[] nextLongArray(int n) throws IOException {
			long[] array = new long[n];
			for (int i = 0; i < n; i++)
				array[i] = nextLong();
			return array;
		}

		public double[] nextDoubleArray(int n) throws IOException {
			double[] array = new double[n];
			for (int i = 0; i < n; i++)
				array[i] = nextDouble();
			return array;
		}

		public static int[] shuffle(int[] a) {
			int n = a.length;
			Random rand = new Random();
			for (int i = 0; i < n; i++) {
				int tmpIdx = rand.nextInt(n);
				int tmp = a[i];
				a[i] = a[tmpIdx];
				a[tmpIdx] = tmp;
			}
			return a;
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}


Measured memory_bytes: 36508
N=int(input())
xyh=[list(map(int,input().split(' '))) for i in range(N)]
for i in range(101):
    for j in range(101):
        H_0=set([h+abs(x-i)+abs(y-j) for x,y,h in xyh])
        H_1=set([h+abs(x-i)+abs(y-j) for x,y,h in xyh if h!=0])
        if len(H_0)==1:
            print(i,j,max(H_0))
            exit()
        if len(H_1)==1:
            cx,cy,H=i,j,max(H_1)
print(cx,cy,H)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n) for ((i)=1;(i)<=(n);(i)++)
using namespace std;

const int mod=1e9+7;
int n,i,j,lx,ly,fa[200005],bk[200005],ans=1,cnt[200005];
int a[200005],c[200005];
int inv[200005];
struct ball
{
	int x,id;
};
vector<ball> v[200005];
vector<int> s[200005];
bool operator <(ball x,ball y)
{
	if(x.x==y.x) return x.id<y.id;
	return x.x<y.x;
}
int fnd(int x)
{
	if(fa[x]==x)return x;
	return fa[x]=fnd(fa[x]);
}

void inc(int x)
{
	while(x){ans=1ll*ans*x%mod;x--;}
}
void dec(int x)
{
	while(x){ans=1ll*ans*inv[x]%mod;x--;}
}

void upd(int x,int y)
{
	bk[x]=max(bk[x],(int)(upper_bound(v[x].begin(),v[x].end(),(ball){y,n+1})-v[x].begin()-1));
}
int main()
{
	inv[1]=1;for(i=2;i<=200000;i++)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
	cin>>n>>lx>>ly;rep(i,n)fa[i]=i;
	rep(i,n){cin>>c[i]>>a[i];v[c[i]].push_back((ball){a[i],i});}
	rep(i,n) sort(v[i].begin(),v[i].end());
	rep(i,n)if(!v[i].empty()) v[0].push_back(v[i][0]);
	sort(v[0].begin(),v[0].end());
	int mi=c[v[0][0].id];
	for(i=1;i<v[0].size();i++)
	{
		int ths=c[v[0][i].id];
		if(v[mi][0].x+v[ths][0].x>ly) break;
		fa[fnd(v[0][0].id)]=fnd(v[0][i].id);
		upd(ths,ly-v[mi][0].x);
	}
	if(v[0].size()>1)
	{
		int ths=c[v[0][0].id],pre=c[v[0][1].id];
		if(v[pre][0].x+v[ths][0].x<=ly) upd(ths,ly-v[pre][0].x);
	}
	for(i=0;i<v[0].size();i++)
	{
		int ths=c[v[0][i].id];
		upd(ths,lx-v[ths][0].x);
	}
	rep(i,n)if(bk[i])rep(j,bk[i])fa[fnd(v[i][j].id)]=fnd(v[i][0].id);
	rep(i,n)s[fnd(i)].push_back(i);
	rep(i,n)if(!s[i].empty())
	{
		inc(s[i].size());
		for(j=0;j<s[i].size();j++) cnt[c[s[i][j]]]++;
		for(j=0;j<s[i].size();j++)if(cnt[c[s[i][j]]]){dec(cnt[c[s[i][j]]]);cnt[c[s[i][j]]]=0;}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 25716
n = int(input())
s_list = [list(input()) for nesya in range(n)]
a = [50]*26
for s in s_list:
  ho = [0]*26
  for l in s:
    k = ord(l) - ord('a')
    ho[k] += 1
  for i in range(26):
    if a[i] > ho[i]:
      a[i] = ho[i]
for j in range(26):
  if a[j] == 0:
    pass
  else:
    b = chr(j+ord('a'))
    print(b*a[j],end='')
print()

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>

using namespace std;

const int P=1000000007;
const int N=15;
const int S=1<<N;
const int M=N*N;

int f[S],bitcnt[S];
int tov[N];
int pw[M];
int n,m;

void update(int &x,int y){(x+=y)%=P;}

void dp()
{
	f[0]=1;
	for (int s=1;s<1<<n;++s)
		if (!((s&1)^((s>>1)&1)))
		{
			for (int u=s,t;u;u=(u-1)&s)//u sg(x)=0,t sg(x)!=0
			{
				t=s^u;
				if (!((t&1)^((t>>1)&1)))
				{
					int tmp=1;
					for (int i=0;i<n;++i)
						if ((s>>i)&1)
							if ((t>>i)&1) tmp=1ll*tmp*((pw[bitcnt[tov[i]&u]]+P-1)%P)%P;
							else tmp=1ll*tmp*pw[bitcnt[tov[i]&t]]%P;
					update(f[s],1ll*f[t]*tmp%P);
				}
			}
		}
}

int main()
{
	//freopen("daggame.in","r",stdin),freopen("daggame.out","w",stdout);
	scanf("%d%d",&n,&m),pw[0]=1;
	for (int i=1,x,y;i<=m;pw[i]=(pw[i-1]<<1)%P,++i) scanf("%d%d",&x,&y),tov[x-1]|=1<<y-1;
	for (int s=1;s<1<<n;++s) bitcnt[s]=bitcnt[s-(s&-s)]+1;
	dp(),printf("%d\n",(pw[m]+P-f[(1<<n)-1])%P);
	//fclose(stdin),fclose(stdout);
	return 0;
}

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

int main(void) {
  int A, B, C;
  cin >> A >> B >> C;
  bool isYes = false;
  for (int i = 1; i <= B; i++) {
    if (A * i % B == C) {
      isYes = true;
      break;
    }
  }
  cout << (isYes ? "YES" : "NO") << endl;
  return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO 自動生成されたメソッド・スタブ
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str = br.readLine();

		while(str.contains("()")){
			str = str.replaceAll("\\(\\)", "");
		}
		//System.out.println(str);
		char[] input = str.toCharArray();

		int starIndex = 0;

		for(int i = 0; i < input.length; i++){
			if(input[i] == '*'){
				starIndex = i;
			}
		}

		int left = starIndex - 1;
		int right = starIndex + 1;

		int result = 0;
		while(left >= 0){
			if(input[left] == '('){
				while(right <= input.length - 1){
					if(input[right] == ')'){
						result++;
						break;
					}

					right++;
				}
			}

			left--;
		}

		System.out.println(result);
	}

}



Measured memory_bytes: 24612
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <vector>
#include <cstdio>
#include <iomanip>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;i++)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define REP(e,v) for(auto e:v)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>()>
#define pb push_back
#define vec vector<int>
#define vecvec vector<vector<int>>
#define vecll vector<ll>
#define vecvecll vector<vector<ll>>
#define bs binary_search
#define All(c) (c).begin(),(c).end()
#define mp make_pair
using namespace std;
int in(){int x;scanf("%d",&x);return x;}
string stin(){string s;cin>>s;return s;}
ll lin(){ll x;scanf("%lld",&x);return x;}
int main(){
    int n=in(),k=in();
    double ans=0;
    vec c(21);
    rep2(i,1,n){
        int x=(k-1)/i,cnt=0;
        while(x>=1){
            cnt++;
            x/=2;
        }
        ans+=pow(2.0,19-cnt)/n;
    }
    ans/=pow(2.0,19);
    cout<<setprecision(15)<<ans<<endl;
}

Measured memory_bytes: 256
//
//  main.c
//  ITP1_5_B
//
//  Created by k16031kk on 2018/05/21.
//  Copyright © 2018年 AIT. All rights reserved.
//

#include <stdio.h>

int main(int argc, const char * argv[]) {
    // insert code here...
    int H=0, W=0;
    scanf("%d %d", &H, &W);
    while(H!=0 || W!=0) {
        for(int i=0; i<H; i++) {
            for(int j=0; j<W; j++) {
                if(i==0 || j==0 || i==H-1 || j==W-1) {
                    printf("#");
                } else {
                    printf(".");
                }
            }
            printf("\n");
        }
        printf("\n");
        scanf("%d %d", &H, &W);
    }
    
    return 0;
}



Measured memory_bytes: 2036
def nCk(n, k):
  return factorial(n)/factorial(n-k)/factorial(k)

from math import factorial
N = input()
K = int(input())
order = len(N)
diff = order - K 
if order < K:
  print(0)
else:
  s = int(N[0])
  #lower  = factorial(order-1)/factorial(diff-1)/ factorial(K) * (9**K)
  if order - 1 >= K:
    lower = nCk(order - 1, K) * (9**K)
  else:
    lower = 0
  total = lower
  for i in range(1, s):
  #  total += factorial(order-1)/factorial(diff)/ factorial(K-1) * (9**(K-1))
    total += nCk(order - 1, K - 1) * (9**(K-1))

  if K == 1:
    total += 1
  elif K == 2:
    under = int(N[1:])
    num = "0"*(order -1)
    for k in range(order - 1):
      for kk in range(1, 10):
        tmp = num[:k] + str(kk) + num[k+1:]
        if int(tmp) <= under:
          total += 1
  elif K == 3:
    under = int(N[1:])
    num = "0"*(order -1)
    for k in range(1, order - 1):
      for j in range(k):
        for kk in range(1, 10):
          for jj in range(1, 10):
            tmp = num[:j] + str(jj) + num[j+1:k] +str(kk) +  num[k+1:]
            if int(tmp) <= under:
              total += 1


  print(int(total))
  #pattern = factorial(order)/factorial(diff)/ factorial(K) * (9**K)

Measured memory_bytes: 3064
//by Top1
#include <bits/stdc++.h>
          
#define f first
#define s second
#define int long long
#define ld long double
#define ull unsigned long long
#define pii pair <int, int>
#define pll pair <long, long>
#define mp make_pair
#define pb push_back
#define pf push_front
#define pp pop_back
#define cerr cout
#define rev reverse
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define forn(i, a, b) for (int i = a; i <= b; i++)
#define boost ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0);
#define nxtp next_permutation
#define pvtp prev_permutation
#define KZ return 
#define x1 x21212121
#define y1 y21212121
#define sqr(x) x * x 
      
const int inf = (1e9) + 1;
const int mod = 479001599;
const int maxn = 5e5 + 111;
        
using namespace std;          

int n, k, c, l[maxn], r[maxn];
string s;
vector <int> v;

void solve(){ 
	cin >> n >> k >> c >> s;

	for (int i = 0; i < n; i++)
		if (s[i] == 'o')
			v.pb(i + 1);
  
	int x = 1, pos = v[0];
	l[x] = v[0];

	for (int i = 1; i < sz(v); i++){
		if (v[i] - pos > c){
			x++;
			l[x] = v[i];
			pos = v[i];
		}
		if (x == k)
			break;
	}

	if (x < k)
		return;

	x = k, pos = v[sz(v) - 1];
	r[x] = pos;
  	
	for (int i = sz(v) - 1; i >= 0; i--){
		if (pos - v[i] > c){
	    	x--;
	    	r[x] = v[i];
	    	pos = v[i];
		}
		if (x == 1)
			break;
	}


	for (int i = 1; i <= k; i++)
		if (l[i] == r[i])
			cout << l[i] << endl;
}                              
      
main(){
    boost;
    
    int q = 1;
 
    //cin >> q;
    
    while (q--){
        solve();
    }
}

Measured memory_bytes: 9096
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = (n+1)//2
    print(a/n)

if __name__ == '__main__':
    main()

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

template <typename T>
using Matrix = vector<vector<T>>;

template <typename T>
Matrix<T> matrix(int R, int C, T x = T()) { return Matrix<T>(R, vector<T>(C, x)); }

struct Mod
{
    const static auto M = static_cast<int>(1e9+7);
    long long k;

    Mod() = default;
    Mod(long long k) : k(k%M) {}
};

Mod operator+(Mod a, Mod b) { return a.k + b.k; }
Mod& operator+=(Mod& a, Mod b) { return a = a+b; }
Mod operator*(Mod a, Mod b) { return a.k * b.k; }
Mod operator-(Mod a, Mod b) { return a.k - b.k + Mod::M; }

Mod solve(int N, int C, vector<int> A, vector<int> B)
{
    auto power = matrix<Mod>(401, C+1);
    for (auto x = 0; x <= 400; x++)
    {
        power[x][0] = 1;
        for (auto c = 1; c <= C; c++)
            power[x][c] = power[x][c-1] * x;
    }

    auto partial_sums = matrix<Mod>(401, C+1);
    for (auto c = 0; c <= C; c++)
    {
        partial_sums[0][c] = 0;
        for (auto x = 1; x <= 400; x++)
            partial_sums[x][c] = partial_sums[x-1][c] + power[x][c];
    }

    auto ways = vector<Mod>(C+1);
    ways[0] = 1;
    for (auto i = 0; i < N; i++)
    {
        auto nways = vector<Mod>(C+1);

        for (auto c = 0; c <= C; c++)
        {
            for (auto ci = 0; ci <= c; ci++)
            {
                auto factor = partial_sums[B[i]][ci] - partial_sums[A[i]-1][ci];
                nways[c] += factor * ways[c-ci];
            }
        }

        ways = nways;
    }
    return ways[C];
}

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

    auto A = vector<int>(N);
    for (auto& x : A) cin >> x;

    auto B = vector<int>(N);
    for (auto& x : B) cin >> x;

    cout << solve(N, C, A, B).k << endl;
}



Measured memory_bytes: 2816
//Single Source Shortest Path II
#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

static const int N = 10000;
static const int WHITE = 0;
static const int BLACK = 1;
int n, colors[N], d[N];
vector<pair<int, int> > G[N];


void dijkstra() {
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > PQ;
    for(int i = 0; i < N; i++) {
        colors[i] = WHITE;
        d[i] = INT_MAX;
    }
    d[0] = 0;
    PQ.push(make_pair(0, 0));
    while(!PQ.empty()) {
        pair<int, int> f = PQ.top();
        PQ.pop();
        int u = f.second;
        if(colors[u] == BLACK) continue;
        for(int i = 0; i < G[u].size(); i++) {
            if(d[G[u][i].first] > f.first + G[u][i].second) {
                d[G[u][i].first] = f.first + G[u][i].second;
                PQ.push(make_pair(d[G[u][i].first], G[u][i].first));
            }

        }
    }
}

int main() {
    int u, k, v, c;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> u >> k;
        for(int j = 0; j < k; j++) {
            cin >> v >> c;
            G[u].push_back(make_pair(v, c));
        }
    }

    dijkstra();

    for(int i = 0; i < n; i++) {
        cout << i << " " << d[i] << endl;
    }
}


Measured memory_bytes: 8068
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
typedef   long long int ll;
typedef unsigned long long int sll;
typedef  double ld;
#define A 1000000007ll
#define B 998244353ll
#define C 1000000000000000000ll
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define ve vector
#define br break
#define PI 3.1415926535

bool dp[1000005];

int main() 
{
    FAST;
    ll n,k;
    cin>>n>>k;
    ll a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<1000005;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i>=a[j] && dp[i-a[j]])
                dp[i]=1;
        }
        dp[i]=!dp[i];
    }
    if(!dp[k])
        cout<<"First";
    else
        cout<<"Second";
    return 0;
}

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

using namespace std;

typedef unsigned long long int lli;


int main(){
	
	lli r,d,ans=0,n,b;
	cin>>n;
	
	b=n;
	d=b/500;
	ans+=1000*d;
	r=b%500;
	r=r/5;
	ans+=(5*r);
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
from collections import Counter

n = int(input())
v = list(map(int, input().split()))

if len(set(v)) == 1:
    print(n // 2)
else:
    v1 = [v[i] for i in range(0, n, 2)]
    v2 = [v[i + 1] for i in range(0, n, 2)]

    kw1 = Counter(v1)
    kw2 = Counter(v2)

    x1 = kw1.most_common()[0][0]
    x2 = kw2.most_common()[0][0]

    if x1 != x2:
        ans = 0
        for i in v1:
            if i != x1:
                ans += 1
        for i in v2:
            if i != x2:
                ans += 1
    else:
        y1 = kw1.most_common()[1][0]
        y2 = kw2.most_common()[1][0]

        ans1 = 0
        ans2 = 0

        for i in v1:
            if i != y1:
                ans1 += 1
        for i in v2:
            if i != x2:
                ans1 += 1

        for i in v1:
            if i != x1:
                ans2 += 1
        for i in v2:
            if i != y2:
                ans2 += 1

        ans = min(ans1, ans2)

    print(ans)


Measured memory_bytes: 20572
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cmath>
#include <cctype>
#include <stack>
#include <map>
#include <cstring>
#include <sstream>
#include <set>
#include <list>
#include <fstream>
#include <iomanip>
#include <assert.h>

#define ll long long
#define ull unsigned long long
#define pii std::pair<int, int>
#define op                            \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(0);

const int INF = 0x3f3f3f3f;
const int maxn = (100000 + 5);
const int mod = (1000000007);

int main()
{
    op
    std::string s;
    std::cin>>s;
    int a=0,b=0;
    for(int i=0;i<3;i++)
        if(s[i]=='A')
            a++;
        else b++;
    if(a==3||b==3)
        std::cout<<"No\n";
    else std::cout<<"Yes\n";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,m,q;
int pos[21][21];
ll dp[21][(1<<19)];
int mx[(1<<19)];
int main(){
	cin>>n>>m>>q;
	if(n == 1){
		cout<<1<<endl;
		return 0;
	}
	memset(pos,-1,sizeof(pos));
	rep(i,q){
		int a,b,c;
		cin>>a>>b>>c;
		pos[a][b] = c;
	}
	dp[1][0] = 1;
	for(int i=1;i<(1<<19);i++){
		for(int j=18;j>=0;j--){
			if(i >= (1<<j)){
				mx[i] = (1<<j);
				break;
			}
		}
	}
	repn(L,m){
		repn(i,n-1){
			rep(mask,(1<<(n-1))){
				if(dp[i][mask] == 0) continue;
				if(pos[L][i] != 1 && mask < (1<<(n-2))){
					int mask2 = mask%(1<<(n-2));
					mask2 *= 2;
					dp[i+1][mask2] += dp[i][mask];
				}
				if(pos[L][i] != 0){
					int mask2 = mask;
					if(mask >= (1<<(i-1))){
						mask2 = mask-mx[mask];
					}
					mask2 = mask2%(1<<(n-2))*2+1;
					dp[i+1][mask2] += dp[i][mask];
				}
			}
		}
		rep(mask,(1<<(n-1))){
			dp[1][mask] = dp[n][mask]%mod;
		}
		for(int i=2;i<=n;i++) rep(mask,(1<<(n-1))) dp[i][mask] = 0;
	}
	ll ans = 0;
	rep(mask,(1<<(n-1))) ans = (ans+dp[1][mask])%mod;
	cout<<ans<<endl;
}

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

int main()
{
    char s[200001];

    scanf("%s",s);

    int len = strlen(s),i,j;
    for (i = 0; i < len; i++)
    {
        if (s[i] == 'A')
        {
            break;
        }
    }
    for (j = len - 1; j >= 0; j --)
    {
        if(s[j] == 'Z')
        {
            break;
        }
    }
    
    printf("%d",j - i + 1);
}

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

using namespace std;
 
int main(){
    int x[110];
    int N, K, i;
    int ans = 0;
    cin >> N >> K;
    for (i = 0; i < N; i++){
        cin >> x[i];
        ans += 2 * min(x[i], K - x[i]);
    }
    cout << ans << endl;

}

Measured memory_bytes: 256
import std.stdio;
import std.string;

size_t lb(int[10][] arr, int n, int key) {
	long left = -1;
	long right = arr.length;

	while(right - left > 1) {
		long mid = left + (right - left) / 2;
		if (arr[mid][n] >= key) right = mid;
		else left = mid;
	}
	return right;
}

void main() {
	int n;
	scanf("%d\n", &n);
	auto s = readln.chomp;
	int[10][] lad = new int[10][n];

	foreach(j; 0..10) {
		if (j == s[0] - 48) {
			++lad[0][j];
		}
	}
	foreach(i; 1..n) {
		foreach(j; 0..10) {
			lad[i][j] = lad[i-1][j];
			if (j == s[i] - 48) {
				++lad[i][j];
			}
		}
	}
	int cnt;
	foreach(i; 0..10) {
		foreach(j; 0..10) {
			foreach(k; 0..10) {
				auto si = lb(lad, i, 1);
				if (si >= n) continue;
				auto sj = lb(lad, j, 1 + lad[si][j]);
				if (sj >= n) continue;
				auto sk = lb(lad, k, 1 + lad[sj][k]);
				if (sk < n)
					++cnt;
			}
		}
	}
	cnt.write;
}


Measured memory_bytes: 3452
def w(ar,be,le)
    #pp "ar = #{ar}, be = #{be}, le = #{le}"
    if(le == 0 || ar.length < be+le-1)then return 0 end
    flag = 0
    flag2 = 0
    le.times do |i|
        if ar[be+i] >= 1 then
            flag = 1
        else
            flag2 = 1
        end
        #pp "now i = #{i}, flag = #{flag}, flag2 = #{flag2}"
    end
    if flag == 0 then return 0 # 全て 0 だった場合、水やりができないため 0 を返す
    end
    if flag2 == 0 then # 全てが 1 以上だった場合、すべてに水やりをするため w 関数を再帰呼び出しする
        le.times do|i|
            ar[be+i] -= 1
        end
        return w(ar,be,le) + 1
    end
    
    # まず0じゃないところまで be をずらす #
    count = 0
    while ar[be] <= 0 do
        be +=1
        le -=1
    end
    # 次に 0 のところを見つけて再帰呼び出しをする #
    i = be+1
    flag = 1 # 0 が見つけられなかった場合のフラグ
    while i < (be + le) do
        if ar[i] == 0 then
            count += w(ar,be,i-be) # 0 より前の要素を再帰呼び出し
            count += w(ar,i+1, le-(i-be+1)) # 0 より後の要素を呼び出し
            flag = 0
            break
        end
        i += 1
    end
    if flag == 1 then count += w(ar,be,le) end
    return count
end

len = gets.chomp!.to_i
arr = gets.chomp!.split.map &:to_i

puts w(arr,0,len)

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

int main() {
    int n;
    cin >> n;
    vector<int> b(n-1);
    rep(i,n-1) cin >> b[i];
    vector<int> a(n);
    a[0] = b[0];
    for(int i = 1; i <= n-2 ; ++i){
        a[i] = min(b[i], b[i-1]);
    }
    a[n-1] = b[n-2];
    int ans = 0;
    rep(i,n) ans+=a[i];
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
#define rep(i, n) for (ll i = 0; i < (n); i++)
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
#ifndef ONLINE_JUDGE
    #define debug(x) cerr << #x << ": " << x << endl;
#else
    #define debug(x)
#endif

int main() {
    cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(20);

    ll N;
    cin >> N;

    ll ans = 0;
    // L固定した時の頂点の個数の和
    for(ll i = 1; i <= N; i++) ans += (N+1-i) * (N+2-i) / 2;

    rep(i,N-1) {
        ll x, y;
        cin >> x >> y;
        if(x > y) swap(x, y);
        ans -= x * (N+1-y);
    }
    cout << ans << endl;
}


Measured memory_bytes: 3660
# -*- coding: utf-8 -*-
def main():
    N, Y = map(int, input().split())
    now = 0
    check = 0
    for i in range(0, N + 1):
        for j in range(0, N+1-i):
            k = N - i - j
            sum = 10000*i + 5000*j + 1000*k
            
            if sum == Y:
                print(str(i) + ' ' + str(j) + ' ' + str(k))
                return
            elif sum > Y:
                break
    print('-1 -1 -1')
    return
                
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 9196
#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 pi = pair<int,int>;
using mp = map<int,int>;
using ump = unordered_map<int,int>;
#define MOD 1000000007

#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update > ordered_set;

#define dbg(args...) do {cerr<<#args<<" : "; faltu(args); } while(0)
void faltu ()  {        cerr << endl;}
template < typename T, typename ... hello>void faltu( T arg, const hello &... rest) {cerr<<arg<< ' ';faltu(rest...);}

#define fastio  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int main(){
    fastio;
    ///freopen("input.txt","r",stdin);
    ///freopen("output.txt","w",stdout);
    ll n; string za;
    cin>>n>>za;
    if(za.size()>n){
        string st="...";
        string el = za.substr(0,n)+st;
        cout<<el<<endl;
    }
    else
        cout<<za<<endl;
return 0;
}


Measured memory_bytes: 3656
#include<bits/stdc++.h>
using namespace std;
	
	#define 	ll 						long long int
	#define 	REP(i,a,b)				for(i=a;i<=b;i++)
	#define 	REPr(i,b,a)				for(i=b;i>=a;i--)
	#define 	pb 						push_back
    #define 	mp 						make_pair
    #define 	f  						first
   	#define 	s  						second
   	#define 	umap(type1,type2)		unordered_map<type1,type2>

int mod = pow(10,9)+7;

void solve(){
	ll k;	cin>>k;
	ll digit=k%10;
	if(digit!=1 && digit!=3 && digit!=7 && digit!=9){
		cout<<-1<<endl;
		return;
	}	
	if(k==1 || k==7){
		cout<<1<<endl;
		return;
	}

	ll rem=7;
	ll z=7;
	ll cnt=1;

	while(rem!=0){
		z=(z*10)%k;
		rem=(rem+z)%k;
		cnt++;
	}

	cout<<cnt<<endl;
}

void pb_18(){
	#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
	#endif

	/***************************

		FuCk RATINGS I am in love with EXPERIENCE.

	***************************/

	int t;	t=1;
	while(t--)	solve();
}

int main(){
	pb_18();
}

Measured memory_bytes: 3608
#include <stdio.h>
#define N 100001

typedef struct{
  int par;
  int left;
  int right;
}node;

node T[N];

int dep(int);
int hei(int);

int main(){
  int n,i,j,a;

  scanf("%d",&n);

  for(i=0; i<n; i++) T[i].par = T[i].left = T[i].right =-1;

  for(i=0; i<n; i++){
    scanf("%d",&a);
    scanf("%d %d", &T[a].right, &T[a].left);
    if(T[a].left != -1) T[T[a].left].par = a;
    if(T[a].right != -1) T[T[a].right].par = a;
  }

  for(i=0; i<n; i++){
    printf("node %d: parent = %d, sibling = ", i ,T[i].par);
    if(T[i].par == -1){
      printf("-1, ");
    }else{
      if(T[T[i].par].left == i){
	printf("%d, ",T[T[i].par].right);
      }else{
	printf("%d, ",T[T[i].par].left);
      }
    }
    printf("degree = ");
    if(T[i].left == -1 && T[i].right == -1){
      printf("0, ");
    }else{
      if(T[i].left != -1 && T[i].right != -1){
	printf("2, ");
      }else{
	printf("1, ");
      }
    }
    printf("depth = %d, height = %d, ", dep(i), hei(i));
    if(T[i].par == -1){
      printf("root");
    }else{
      if(T[i].left ==-1 && T[i].right == -1){
	printf("leaf");
      }else{
	printf("internal node");
      }
    }
    printf("\n");
  }

  return 0;
}


int dep(int n){
  if(T[n].par == -1) return 0;
  return dep(T[n].par)+1;
}

int hei(int n){
  int right=0,left=0;
  if(T[n].right == -1 && T[n].left == -1) return 0;

  if(T[n].right != -1) right = hei(T[n].right)+1;
  if(T[n].left != -1) left = hei(T[n].left)+1;

  if(left > right) return left;
  else return right;
}

Measured memory_bytes: 604