akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

D = int(input().strip())
C = list(map(int,input().split()))
S = [list(map(int, input().split())) for _ in range(D)]

ans = 0
score = 0
last = [[-1] for i in range(26)]
schedule = []

for d in range(D):
  t = d%26
  last[t].append(d)
  score += S[d][t]
  schedule.append(t)

for i in range(26):
  last[i].append(D)
  for k in range(len(last[i])-1):
    g = last[i][k+1]-last[i][k]-1
    score -= C[i]*g*(g+1)//2

count = 1000000
import random
while count:
  count -= 1
  prev = score
  d,q = random.choice(range(D)),random.choice(range(26))
  p = schedule[d]
  schedule[d] = q
  score -= S[d][p]
  score += S[d][q]
  
  pos = last[p].index(d)
  score -= C[p]*(last[p][pos]-last[p][pos-1])*(last[p][pos+1]-last[p][pos])
  last[p].remove(d)
  
  pos = bisect.bisect(last[q],d)
  score += C[q]*(d-last[q][pos-1])*(last[q][pos]-d)
  bisect.insort(last[q],d)
  if score<prev:
    score = prev
    bisect.insort(last[p],d)
    last[q].remove(d)
    schedule[d] = p
    
for i in schedule:
  print(i+1)

Measured memory_bytes: 83500
N = int(input())
array = [list(map(int, input().split())) for _ in range(N)]

dp = [[0] * 3 for i in range(N)]

# i日目にjを選択した時の最大値を計算する
for i in range(N):
    for j in range(3):
        if i == 0:
            dp[i][j] = array[i][j]
            continue
        for k in range(3):
            if j != k:
                sum = dp[i - 1][k] + array[i][j]
                dp[i][j] = sum if sum > dp[i][j] else dp[i][j]

print(max(dp[N - 1]))


Measured memory_bytes: 104880
#include <bits/stdc++.h>
using namespace std;
#define fol(i,n) for(int i=0;i<n;i++)
#define pb push_back
typedef long long ll;
typedef pair<int,int> P;
typedef vector<P> vip;

int main(){
  int t,x;cin>>t>>x;
  double ans = (double)t/x;
  cout <<ans << endl;
  return 0;
}


Measured memory_bytes: 256
// C++ code to find maximum possible product of 
// sub-sequence of size k from given array of n 
// integers 
#include <algorithm> // for sorting 
#include <iostream> 
using namespace std; 
#define ll long long int
#define MOD 1000000007

ll xmod(ll a){
    return ((a%MOD)+MOD)%MOD;
}

// Required function 
ll maxProductSubarrayOfSizeK(ll A[], ll n, ll k) 
{ 
	// sorting given input array 
	sort(A, A + n); 

	// variable to store final product of all element 
	// of sub-sequence of size k 
	ll product = 1; 

	// CASE I 
	// If max element is 0 and 
	// k is odd then max product will be 0 
	if (A[n - 1] == 0 && (k & 1)) 
		return 0; 

	// CASE II 
	// If all elements are negative and 
	// k is odd then max product will be 
	// product of rightmost-subarray of size k 
	if (A[n - 1] <= 0 && (k & 1)) { 
		for (int i = n - 1; i >= n - k; i--) 
			product = xmod(product*A[i]); 
		return product; 
	} 

	// else 
	// i is current left pointer index 
	int i = 0; 

	// j is current right pointer index 
	int j = n - 1; 

	// CASE III 
	// if k is odd and rightmost element in 
	// sorted array is positive then it 
	// must come in subsequence 
	// Multiplying A[j] with product and 
	// correspondingly changing j 
	if (k & 1) { 
		product = xmod(product*A[j]); 
		j--; 
		k--; 
	} 

	// CASE IV 
	// Now k is even 
	// Now we deal with pairs 
	// Each time a pair is multiplied to product 
	// ie.. two elements are added to subsequence each time 
	// Effectively k becomes half 
	// Hence, k >>= 1 means k /= 2 
	k >>= 1; 

	// Now finding k corresponding pairs 
	// to get maximum possible value of product 
	for (int itr = 0; itr < k; itr++) { 

		// product from left pointers 
		ll left_product = A[i] * A[i + 1]; 

		// product from right pointers 
		ll right_product = A[j] * A[j - 1]; 

		// Taking the max product from two choices 
		// Correspondingly changing the pointer's position 
		if (left_product > right_product) { 
            left_product = xmod(left_product);
			product = xmod(product*left_product); 
			i += 2; 
		} 
		else { 
            right_product = xmod(right_product);
			product = xmod(product*right_product); 
			j -= 2; 
		} 
	} 

	// Finally return product 
	return product; 
} 

// Driver Code to test above function 
int main() 
{ 
	ll n, k;
    cin >> n >> k;
    ll A[n];
    for(ll i=0; i<n; i++){
        cin >> A[i];
    }
	cout << maxProductSubarrayOfSizeK(A, n, k); 

	return 0; 
} 


Measured memory_bytes: 5188
import sys
## io
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))
## dp
INIT_VAL = 0
DP2 = lambda d1, d2: [[INIT_VAL]*d2 for _ in range(d1)]
DP3 = lambda d1, d2, d3: [[[INIT_VAL]*d3 for _ in range(d2)] for _ in range(d1)]

def main():
    res = ''
    for i in range(3): res += IS()[i]
    print(res)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
def main():
    N = int(input())
    h = list(map(int, input().split()))
    now_h = []
    for _ in range(N):
        now_h.append(0)
    i = 0
    count = 0
    while True:
        if now_h[i] < h[i]:
            # ノルマに達していない
            end = i
            for j in range(i + 1, N):
                if now_h[j] < h[j]:
                    end = j
                else:
                    break
            for k in range(i, end + 1):
                now_h[k] += 1
            count += 1
        else:
            if i == N - 1:
                break
            i += 1
            continue
    print(count)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
N, M = [int(i) for i in input().split()]
H_list = [int(i) for i in input().split()]

cnt = 0
tendai_hight = {}
tendai_good = {}

for i, h in enumerate(H_list):
    tendai_hight[i+1] = h
    tendai_good[i+1] = 0
    
# 道の数だけループ
while cnt < M:
    cnt += 1
    A, B = map(int, input().split())
    # 比較して低い方に負けフラグ1を立てる
    if tendai_hight[A] < tendai_hight[B]:
        tendai_good[A] = 1
    if tendai_hight[A] > tendai_hight[B]:
        tendai_good[B] = 1       
    # 比較して同じならば両方に負けフラグ1を立てる
    if tendai_hight[A] == tendai_hight[B]:
        tendai_good[A] = 1
        tendai_good[B] = 1
        
result = [key for key ,value in tendai_good.items() if value != 1]
print(len(result))

Measured memory_bytes: 32964
import numpy as np

INF = 1000000007

def add(x, y):
	return (x + y) % INF

def sub(x, y):
	return (x - y) % INF

def mul(x, y):
	return (x * y) % INF

def power(x, y):
	return pow(x, y, INF)

def div(x, y):
	return mul(x, power(y, INF - 2))


N, A, B, C = map(int, input().split())
A = div(A, 100 - C)
B = div(B, 100 - C)
C = div(C, 100)

FACT = [1]
A_ACC = [1]
B_ACC = [1]
for i in range(1, 2*N):
	FACT.append(mul(FACT[i-1], i))
	A_ACC.append(mul(A_ACC[i-1], A))
	B_ACC.append(mul(B_ACC[i-1], B))

def NCK(n, k):
	if n < k:
		return 0
	return div(FACT[n], mul(FACT[n-k], FACT[k]))
	

k = div(1, sub(1, C))

ans = 0
for i in range(N):
	ans = add(
		ans,
		mul(
			i + N,
			mul(
				NCK(N+i-1, i),
				add(
					mul(A_ACC[N], B_ACC[i]),
					mul(A_ACC[i], B_ACC[N])
				)
		)))
ans = mul(ans, k)
print(ans)


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

int comb_mod2(int n, int k){
//	printf("(n, k) = (%lld, %lld)\n", n, k);
	return n >= 0 && 0 <= k && k <= n && (n & k) == k;
/*	if(n < 0 || k < 0 || n < k){
		return 0;
	}
	else{
		return (n & k) == k;
	}*/
}

signed main(){
	int N, i;
	scanf("%lld", &N);
	vector<int> x(N), y(N);
	int M = 0;
	for(i = 0; i < N; i++){
		scanf("%lld%lld", &x[i], &y[i]);
		M = max(M, max(abs(x[i]), abs(y[i])));
	}
	int T = 1;
	while(T < 3 * M){
		T = 2 * T + 1;
	}
//	printf("(M, T) = (%lld, %lld)\n", M, T);
	int l = -(M + 1), h, r = 2 * M;
	while(r - l > 1){
		h = (l + r) / 2;
//		printf("h = %lld\n", h);
		int is_black = 0;
		for(i = 0; i < N; i++){
			is_black ^= comb_mod2(y[i] + T, h - x[i]);
//			printf("is_black[%lld] = %lld\n", i, is_black);
		}
//		printf("is_black = %lld\n", is_black);
		if(is_black == 1){
			r = h;
		}
		else{
			l = h;
		}
	}
	printf("%lld\n", r);
	return 0;
}

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

int main() {
 int n ;
  int ans = 0;
  string s;
  cin >> n >> s ;
  for(int i=0;i<n-2;i++){
  
    
    if ((s.at(i)=='A') && (s.at(i+1)=='B') && (s.at(i+2)=='C'))
      ans ++ ;
  }
  cout <<ans ;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.Arrays;
class Main{
    public static void main(String[] args) throws IOException {
        int i,j,k;
        long sum;
        int[][] A = new int[101][101];
        int[][] B = new int[101][101];
        int[] n = new int[990];
        String[] str = new String[990];
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        str = in.readLine().split(" ");
        for(i=0;i<3;i++){
            n[i]=Integer.parseInt(str[i]);   
        }
        for(i=0;i<n[0];i++){
            str = in.readLine().split(" ");
            for(j=0;j<n[1];j++){
                A[i][j]=Integer.parseInt(str[j]);
            }
        }
        for(i=0;i<n[1];i++){
            str = in.readLine().split(" ");
            for(j=0;j<n[2];j++){
                B[i][j]=Integer.parseInt(str[j]);
            }
        }
        for(i=0;i<n[0];i++){
            for(j=0;j<n[2];j++){
                sum=0;
                for(k=0;k<n[1];k++){
                    sum += B[k][j]*A[i][k];             
                }
                if(j!=0) System.out.print(" ");
                System.out.print(sum);
            }
            System.out.println();
        }      
        System.out.flush();
    }
}

Measured memory_bytes: 37620
#include <iostream>
using namespace std;
int main(void){
   int a,b;
   cin>>a>>b;
   if(b%2==1){
       cout<<"No"<<endl;
   }
   else if(b<2*a){
       cout<<"No"<<endl;
   }
   else if(4*a<b){
       cout<<"No"<<endl;
   }
   else{
       cout<<"Yes"<<endl;
   }
    
}


Measured memory_bytes: 3592
#include<bits/stdc++.h>
#define endl '\n'
#define mod 1000000007
typedef long long int ll;
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    while(t--){
	   int n,m,k;
	   cin>>n>>m>>k;
	   vector<int> a(n);
	   for(auto &it : a) cin>>it;
	   vector<int> b(m);
	   for(auto &it : b) cin>>it;
	   
	   vector<ll> prefix_A(n+1);
	   vector<ll> prefix_B(m+1);
	  for(int i=0;i<n;i++){
		   prefix_A[i+1] = prefix_A[i] + a[i];
	   }
	   for(int i=0;i<m;i++){
		   prefix_B[i+1] = prefix_B[i] + b[i];
	   }
	   int total=0;
	   for(int i=0;i<=n;i++){
		   ll other = k-prefix_A[i];
		   if(other<0)
			   continue;
		   int l=lower_bound(prefix_B.begin(),prefix_B.end(),other)-prefix_B.begin();
		   if(l>m or prefix_B[l]>other)
			   --l;
		   total=max(total,i+l);
	   }
	   if(k==1 and a[0]>k)
		   cout<<0;
	   else	   
	   cout<<total<<endl;



    }
    return 0;
} 


Measured memory_bytes: 7928
#include<bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vector<int> >
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
using ll = long long;
using ld =long double;
#define int ll
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
typedef pair<int,pii> piii;
#define mp make_pair
signed main(){
    int h,w; cin>>h>>w;
    if(h==w&&w==1)cout<<1<<endl;
    else if(h==1)
        cout<<w-2<<endl;
    else if(w==1)
        cout<<h-2<<endl;
    else
        cout<<(h*w)-2*(h+w)+4<<endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
    char s[16], d[26];
    scanf("%s", s);
    for(char* p=d, c='A'; c<='Z'; ++c) if (!strchr("ACGT", c)) *p++=c;

    int res=0;
    for(char* p=strtok(s, d); p; p=strtok(NULL, d)) res=max(res, (int)strlen(p));
    printf("%d\n", res);
}

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

vector<vector<bool>>x(8,vector<bool>(8));
int dfs(int v,int N,bool visited[8]){
  bool all_visited=true;
  rep(i,N){
    if(visited[i]==false){
      all_visited=false;
    }
  }
  if(all_visited){
    return 1;
  }
  int ans=0;
  rep(i,N){
    if(x[v][i]==false){
      continue;
    }
    if(visited[i]){
      continue;
    }
    
    visited[i]=true;
    ans+=dfs(i,N,visited);
    visited[i]=false;
  }
  return ans;
}

int main() {
  int n,m;
  cin >> n>>m;
  
  vector<int>a(m),b(m);
  rep(i,m){
    cin>>a.at(i)>>b.at(i);
    a.at(i)--;
    b.at(i)--;
  }
  
  rep(i,m){
    x.at(a.at(i)).at(b.at(i))=true;
    x.at(b.at(i)).at(a.at(i))=true;    
  }
  bool visited[8];
  rep(i,8){
    visited[i]=false;
  }
  visited[0]=true;
  
  cout<<dfs(0,n,visited)<<endl;
 
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef istringstream ISS;
typedef ostringstream OSS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

#define EACH( it, c ) for ( auto it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()
#define DRANGE( c, p ) (c).begin(), (c).begin() + p, (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define DEBUG( x ) cerr << __FILE__ << ":" << __LINE__ << ": " << #x << " = " << ( x ) << endl

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

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

	while ( true )
	{
		int t, n;
		cin >> t >> n;

		if ( !( t | n ) )
		{
			break;
		}

		vector<PII> objects;
		REP( i, 0, n )
		{
			int x, y;
			cin >> x >> y;
			objects.PB( MP( x, y ) );
		}
		sort( ALL( objects ) );

		int sx, sy;
		cin >> sx >> sy;

		queue<PII> que;
		que.push( MP( sx, sy ) );
		map<PII,int> distance;
		distance[ MP( sx, sy ) ] = 0;

		while ( !que.empty() )
		{
			auto cur = que.front();
			que.pop();

			if ( distance[ cur ] == t )
			{
				continue;
			}

			REP( d, 0, 6 )
			{
				auto next( cur );
				next.fst += dx[d];
				next.snd += dy[d];

				if ( !binary_search( ALL( objects ), next ) && !EXIST( distance, next ) )
				{
					que.push( next );
					distance[ next ] = distance[ cur ] + 1;
				}
			}
		}

		cout << distance.size() << endl;
	}

	return 0;
}

Measured memory_bytes: 1348
#include<stdio.h>

int main() {
  int N, T, min;
  scanf("%d %d", &N, &T);
  int c[N], t[N];
  for(int i = 0; i < N; i++) {
    scanf("%d %d", &c[i], &t[i]);
  }
  min = 1001;
  for(int i = 0; i < N; i++) {
    if(c[i] < min && t[i] <= T) {
      min = c[i];
    }
  }
  
  if(min == 1001) {
    printf("TLE\n");
  } else {
    printf("%d\n", min);
  }
}

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

int main() {
  int n;
  cin >> n;
  vector <int> vec((int)pow(10, 5), 0);
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    if (a == 0) {
      vec.at(a)++;
      vec.at(a+1)++;
    } else if (a == vec.size()-1) {
      vec.at(a)++;
      vec.at(a-1)++;
    } else {
      vec.at(a-1)++;
      vec.at(a)++;
      vec.at(a+1)++;
    }
  }
  cout << *max_element(vec.begin(), vec.end()) << endl;
}

Measured memory_bytes: 640
#include <algorithm>
#include <cmath>
#include <iostream>
#include <numeric>
#include <utility>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    cout << (a - 1) * (b - 1) << endl;
}


Measured memory_bytes: 256
import math 

n = int(input())

ac, re, wa, tle = 0, 0, 0, 0

for i in range(n):
	s = input()
	if s == "AC":
		ac += 1
	elif s == "RE":
		re += 1
	elif s == "WA":
		wa += 1
	else:
		tle += 1

print('AC x', ac)
print('WA x', wa)
print('TLE x', tle)
print('RE x', re)


Measured memory_bytes: 69864
#include "bits/stdc++.h"
using namespace std;
#define fol(i,n) for(int i=0;i<n;i++)
#define all(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int,int> P;
typedef vector<P> vip;
int main(){
  int x;
  cin >>x;
  cout << "ABC" <<x <<endl;
  return 0;
}


Measured memory_bytes: 256
N = int(input())
digits = 1
dp = []
dp.append([i for i in range(1,10)])
K = 9

if(N<=9):
    print(dp[0][N-1])
    exit(0)
else:
    N -= 9

while(N>0):
    tmp = []
    for n in dp[digits-1]:
        base = int(str(n)[-1])
        for i in [-1,0,1]:
            if(base+i >= 0 and base+i<10):
                tmp.append(int(str(n)+str(base+i)))
    digits += 1
    K = len(tmp)
    N -= K
    dp.append(tmp)

print(dp[digits-1][N-1])

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

int main(void){
  int n;
  cin >> n;
  double ans = 0;
  double x;
  string u;
  for(int i = 0; i < n; i++){
    cin >> x >> u;
    if(u == "JPY") ans += x;
    else ans += x * 380000.0;
  }
  cout << ans << endl;
  return 0;
}


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

int main(){
	int a,b,c,x;
	cin>>a>>b>>c>>x;
	int temp,ans=0;
	for (int i = 0; i <= a; i++){
		for (int j = 0; j <= b; j++){
			for (int k = 0; k <= c; k++){
				temp = i*500+j*100+k*50;
				if(temp==x)ans++;
			}
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const LL N = 1000000+10;
LL ch[N][2], tot;
LL n, L;
char s[N];
void insert(LL len, char * s) {
    LL now = 0; 
    for (LL i = 1; i <= len; i ++) {
        LL f = (s[i] == '1') ? 1 : 0;
        if (!ch[now][f]) {
            ch[now][f] = ++ tot;
        }
        now = ch[now][f];
    }
}
LL dfs(LL x, LL dep) {
    if (dep > L) return 0;
    if (x == 0 && dep != 0) {
        return (L-dep+1)&(-L+dep-1);
    }
    return dfs(ch[x][0], dep + 1) ^ dfs(ch[x][1], dep + 1);
}
int main() {
    scanf("%lld %lld", &n, &L);
    for (LL i = 1; i <= n; i ++) {
        scanf("%s", s+1);
        LL len = strlen(s+1);
        insert(len, s);
    }
    printf("%s\n", dfs(0, 0) ? "Alice" : "Bob");
}





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

int main(){
  int N;
  cin >> N;
  char S[N], T[N];
  cin >> S >> T;
  for(int i=0; i<N; i++){
    cout << S[i];
    cout << T[i];
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 256
n = int(input())
f = [list(map(int, input().split())) for _ in range(n)]
p = [list(map(int, input().split())) for _ in range(n)]

ans = -float("inf")
for i in range(1, 2 ** 10):
    i_bin = "{:010b}".format(i)
    sm = 0
    for shop_i in range(n):
        cnt = 0
        for j, dig in enumerate(i_bin):
            if f[shop_i][j] * int(dig):# == 1
                cnt += 1
        sm += p[shop_i][cnt]
    ans = max(ans, sm)
        
print(ans)


Measured memory_bytes: 3064
#include  <cstdio>
using namespace std;
#define INF (1<<29)
int N,M,R;
int d[201][201];
int r[9];
int A,B,C;
int  res;
bool used[201];

void dfs(int c, int las, int dist) {
    if (c==R) {
        if (res >dist)
            res=dist;
        return;
    }
    for (int i=1;i<=R;i++)
        if(!used[r[i]]){
            used[r[i]]=true;
            if(las==-1)
                dfs(c+1,r[i],0);
            else
                dfs(c+1,r[i],dist+d[las][r[i]]);
            used[r[i]]=false;
        }
}

int main(){
    scanf("%d%d%d",&N,&M,&R);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            if(i!=j)
                d[i][j]=INF;
    for(int i=1;i<=R;i++)
        scanf("%d",&r[i]);
    for(int i=1;i<=M;i++){
        scanf("%d%d%d",&A,&B,&C);
        if(d[A][B]>C)
            d[A][B]=d[B][A]=C;
    }
    for(int k=1;k<=N;k++)
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++)
                if(d[i][j]>d[i][k]+d[k][j])
                    d[i][j]=d[i][k]+d[k][j];
    res=INF;
    dfs(0,-1,0);
    printf("%d\n",res);
}

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

#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define RFOR(i, a, b) for (int i = (b)-1; i >= int(a); --i)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, int(n) + 1)
#define RREP(i, n) RFOR(i, 0, n)
#define RREP1(i, n) RFOR(i, 1, int(n) + 1)
#define ALL(c) begin(c), end(c)

int _ = (
#ifndef LOCAL
    std::cin.tie(nullptr), std::ios::sync_with_stdio(false),
#endif
    std::cout.precision(10), std::cout.setf(std::ios::fixed));

using ll = long long;
using ull = unsigned long long;
using ld = long double;
template <typename T> using vec = std::vector<T>;
using namespace std;

int main() {
  ll N, a;
  cin >> N;
  unordered_map<int, int> m;
  REP(i, N) {
    cin >> a;
    m[a]++;
    m[a - 1]++;
    m[a + 1]++;
  }

  const auto res = max_element(ALL(m), [](const auto &lhs, const auto &rhs) {
                     return lhs.second < rhs.second;
                   })->second;
  cout << res << endl;
  return 0;
}


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

int main()
{
    int x, n;
    cin >> n;
    if(n%1000 == 0)
    {
        x = 0;
    }
    else
    {
        x = 1000 - (n%1000);
    }

    cout << x <<endl;
    return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
typedef long long ll;
#define REP(i,a) for(int i = 0; i < (a); i++)
using namespace std;

int main(){
	int a,b,x;
	cin >> a >> b >> x;
	if(a <= x && x <= a + b) cout << "YES" << endl;
	else cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <stack>
#include <sstream>

using namespace std;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)


typedef long long int ll;
typedef pair<int, int> Pii;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<double, double> Pdd;
typedef pair<ll, ll> P;
typedef pair<P, ll> PP;


const ll mod = 1e9+7;
const ll INF = 2e9;
const double epsilon = 1e-7;
const double PI = 3.1415926535;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

int main(){
  ll n,q,time=0;
  cin>>n>>q;

  queue<string> w;
  ll t;
  map<string,ll> mp;

  vector<string> nt(n);
  rep(i,n){
    cin>>nt[i]>>t;
    mp[nt[i]]=t;
    w.push(nt[i]);
  }

  string a;

  while(!w.empty()){
    a=w.front();
    // cout<<a<<endl;
    w.pop();
    if(mp[a]>q){
      mp[a]-=q;
      time+=q;
      w.push(a);
    }else{
      time+=mp[a];
      cout<<a<<' '<<time<<endl;
    }
  }










}



Measured memory_bytes: 9148
import java.util.Scanner;


public class Main {
	public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
for(int i=1; i<=10000;i++)
{
int a= sc.nextInt();
if(a==0) break;
System.out.println("Case " + i + ": "+ a);
}

}
}


Measured memory_bytes: 40880
a,b = map(int,input().split())
c = [1,3,5,7,8,10,12]
d = [4,6,9,11]
e = [2]
if (a in c and b in c) or (a in d and b in d)or (a in e and b in e):
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int y = sc.nextInt();
		for(int i=0;i <= x;i++) {
			int leg = (2 * i) + (4 *(x-i));
			if(leg == y) {
				System.out.println("Yes");
				return;
			}
		}
		System.out.println("No");
	}
}

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

using namespace std;

typedef long long ll;

int n;
int a[20], b[20];
int ans = 1e6;

int DP[1<<18][18];

int getVal(int x, int y){
    if((x+y)&1) return a[y];
    return b[y];
}

int main(){
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%d", &a[i]);
    }
    for(int i=0; i<n; i++){
        scanf("%d", &b[i]);
    }

    for(int i=1; i<(1<<n); i++){
        int pcnt = __builtin_popcount(i);
        if(pcnt == 1){
            for(int j=0; j<n; j++){
                if(i&(1<<j)) DP[i][j] = 0;
                else DP[i][j] = 1e6;
            }
            continue;
        }
        for(int j=0; j<n; j++){
            DP[i][j] = 1e6;
            if(!(i&(1<<j))) continue;
            int addInv = 0;
            for(int k=0; k<n; k++){
                if(!(i&(1<<k))) continue;
                if(j < k) addInv++;
            }

            for(int k=0; k<n; k++){
                if(!(i&(1<<k))) continue;
                if(getVal(pcnt, j) >= getVal(pcnt-1, k)){
                    DP[i][j] = min(DP[i][j], DP[(i-(1<<j))][k] + addInv);
                }
            }
        }
    }
    for(int i=0; i<n; i++) ans = min(ans, DP[(1<<n)-1][i]);
    printf("%d", ans==1e6?-1:ans);
}


Measured memory_bytes: 18688
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
using ll=long long;
#define rep(i,a,b) for(int i=(a); i<(b); ++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+b,(a).begin()+c // コンテナ a の 要素 b から c へのイテレータ
// typedef
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

int main() {
	int W, H, N; cin >> W >> H>> N ;

	VVI xya(N, VI(3));
	rep(i, 0, N) {
		scanf("%d %d %d", &xya[i][0], &xya[i][1], &xya[i][2]);
	}

	int w1 = 0, w2 = W, h1 = 0, h2 = H;
	rep(i, 0, N){
		switch (xya[i][2]){
			case 1: w1 = max(xya[i][0], w1); break;
			case 2: w2 = min(xya[i][0], w2); break;
			case 3: h1 = max(xya[i][1], h1); break;
			case 4: h2 = min(xya[i][1], h2); break;
		}
	}
	if (w2 >= w1 && h2 >= h1)
		cout << (w2 - w1) * (h2 - h1) << "\n";
	else cout << 0 << "\n";


	return 0;
}


Measured memory_bytes: 256
H,W=map(x->parse(Int,x),split(readline()))
S=[chomp(readline()) for _=1:H]
flag=true
for i=1:H,j=1:W
  t=0
  for (x,y)=((i+1,j),(i,j+1))
    t+=1<=x<=H&&1<=y<=W&&S[x][y]=='#'
  end
  if t==2
    flag=false
  end
end
println(flag?"Possible":"Impossible")

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

using namespace std;

typedef double D;
typedef long long int LL;

#define st first
#define nd second
#define pb push_back
#define PLL pair <LL, LL>
#define PII pair <int, int>

const int N = 1e6 + 7;
const int MX = 1e9 + 7;
const LL INF = 1e18 + 9LL;

int n;
LL pref[N];

void check(LL &res, int i, int j, int k){
	LL s1 = pref[i], s2 = pref[j] - pref[i];
	LL s3 = pref[k] - pref[j], s4 = pref[n] - pref[k];
	
	LL mn = min(min(s1, s2), min(s3, s4));
	LL mx = max(max(s1, s2), max(s3, s4));
	res = min(res, mx - mn);
}

int ask(int p, int k){
	int from = p - 1, to = k;
	while(from < to){
		int m = (from + to + 1) >> 1;
		if(pref[m] - pref[p - 1] <= pref[k] - pref[m])
			from = m;
		else
			to = m - 1;
	}
	
	return from;
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &pref[i]),
		pref[i] += pref[i - 1];
	
	LL res = INF;
	for(int i = 2; i + 2 <= n; ++i){
		int p1 = ask(1, i);
		int p2 = ask(i + 1, n);
		
		check(res, p1, i, p2);
		check(res, p1 + 1, i, p2);
		check(res, p1, i, p2 + 1);
		check(res, p1 + 1, i, p2 + 1);
	}
	
	printf("%lld\n", res);
	return 0;
}

Measured memory_bytes: 1792
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Text;

class Test
{

    public static void Main()
    {
        var ss = Console.ReadLine();
        List<string> ch = new List<string>(new[] { "dream", "dreamer", "erase", "eraser" });
        
        while(ss!="")
        {
            var ok = false;

            foreach(var word in ch)
            {
                if(!ss.EndsWith(word))
                {
                    continue;
                }

                ss = ss.Remove(ss.Length - word.Length);
                ok = true;
                break;
            }

            if (ok)
                continue;
            Console.Write("NO");
            return;
        }
        Console.Write("YES");
    }

}

















Measured memory_bytes: 37444
#define REP(i, n) for(int i = 0; i < (int)(n); i++)

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

int main() {
	int N;
	int rate[9] = {};
	int num_color = 0;
	int num_color_min = 0;
	int num_color_max = 0;
	cin >> N;
	vector<int> a(N);

	REP(i, N) {
		cin >> a[i];
		rate[min(a[i] / 400, 8)]++;
	}

	REP(i, 8) {
		if (rate[i] != 0) {
			num_color++;
		}
	}

	num_color_min = num_color;
	if (num_color_min == 0 && rate[8] != 0) {
		num_color_min = 1;
	}

	num_color_max = num_color + rate[8];

	cout << num_color_min << " " << num_color_max << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio> 
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=100010;
int tt;
int head[N],to[N],nxt[N],in[N],v[N],fr[N];
inline int gi() {
    int x=0,o=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=='-'?o=-1:0,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
int main() {
    int n,m,tp=0;
    cin>>n>>m;
    for(int i=1;i<n+m;i++) {
	int x=gi(),y=gi();++in[y];
	to[++tt]=y,nxt[tt]=head[x],head[x]=tt;
    }
    for(int i=1;i<=n;i++)
	if(!in[i]) v[++tp]=i;
    while(tp) {
	int x=v[tp--];
	for(int i=head[x];i;i=nxt[i]) {
	    int y=to[i];
	    if(!--in[y]) fr[y]=x,v[++tp]=y;
	}
    }
    for(int i=1;i<=n;i++) printf("%d\n",fr[i]);
    return 0;
}

Measured memory_bytes: 2816
#include <iostream>
#include<iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#define INF 1e9+7
#define rep(i,n) for(int i=0;i<n;i++)
#define NO cout<<"NO"<<endl;
#define YES cout << "YES"<<endl;
#define No cout << "No"<<endl;
#define Yes cout << "Yes"<<endl;
#define all(a) a.begin(),a.end()
#define P pair<int,int>
#define space ' '
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

//(int)'a'は97 (int)'A'は65 (int)'1'は49
//おまじない

const int maxn = 1000;
ll a[maxn+1],c[maxn+1]={0};
ll dp[maxn+1][maxn*10]={0};
ll range=0;
int n,m;

int main(){
    
    cin >> n>>m;
    
    for(int i=1;i<=m;i++){
        int b;
        cin >> a[i]>>b;
        rep(j,b){
            int t;
            cin >> t;
            c[i]+=(1<<(t-1));
        }
    }
    
//    cout << "c[i]"<<endl;
//    for(int i=1;i<=m;i++)cout << c[i]<<space;
//    cout << endl;
    
    for(int i=0;i<n;i++){
        range += (1<<i);
    }
    
//    cout << "range"<<space<<range<<endl;
    
    for(int i=0;i<=m;i++){
        for(int j=0;j<=range;j++){
            if(j==0)dp[i][j]=0;
            else dp[i][j]=INF;
        }
    }
    
    for(int i=1;i<=m;i++){
        for(int j=0;j<=range;j++){
            dp[i][j|c[i]]=min(dp[i][j|c[i]],dp[i-1][j]+a[i]);
            dp[i][j]=min(dp[i-1][j],dp[i][j]);
        }
    }
    
    if(dp[m][range]==INF)cout << -1<<endl;
    else cout << dp[m][range]<<endl;
    
    return 0;
}


Measured memory_bytes: 77184
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define in insert
#define PI 3.1415926535897932384626433832795
#define F first
#define S second
#define aLL(str) (str).begin(), (str).end()
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0)
#define ll long long
#define ld long double
#define lcm(a, b) (a * b) / __gcd(a, b)
#define flu(i, a, b) for(ll i = a; i < b; i++)
#define blu(i, a, b) for(ll i = a; i >= b; i--)
#define upper(s) transform(s.begin(), s.end(), s.begin(), ::toupper)
#define lower(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
#define Unique(X) (X).erase(unique(all(X)), (X).end())
#define all(v) v.begin(), v.end()
#define ull unsigned long long
typedef vector<ll> vl;
typedef map<ll, ll> ml;
typedef vector<string> vs;
typedef vector<vector<int>> vvi;
char e = '\n';

ll MOD = 1e9 + 7;

ll i, j, le;

int sv(int x)
{
    int n = 200000;
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));

    for (int p = 2; p * p <= n; p++)
    {
       
        if (prime[p] == true)
        {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
    if (prime[x])
        return 1;
    else
        return 0;
}

int main()
{
    IOS;
    int t;
    //cin >> t;
     t=1;
    while (t--)
    {
        ll x,k,d;
        cin>>x>>k>>d;
        ll x1= abs(x);
        if((ull)(k*d) <= x1)
        cout<<x1-((ull)k*d)<<e;
        else {
            ll mov= x1/d;
            ll left = x1%d;
            k=k-mov;
            if(k%2==0)cout<<left<<e;
            else cout<<abs(left-d)<<e;
        }
    }
    return 0;
}

Measured memory_bytes: 3512
#include <bits/stdc++.h>
  using namespace std;
  typedef long long int ll;
  #define mod 1000000007
  #define all(v)  v.begin(),v.end()
  #define pb push_back
  #define fast ios_base:: sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
  ll power_mod(ll a,ll x){if(x==0) return 1;ll y=power_mod(a,x/2);ll ans=(y*y)%mod; if(x%2) ans=(ans*a)%mod;return ans;}
  ll inv(ll a){return power_mod(a,mod-2);}
  ll power(ll a, ll x){ if(x==0) return 1; ll y= power(a,x/2); ll ans=(y*y); if(x%2) ans*=a; return ans;}
  

  int main()
  {
     
            int p,q,r;
            cin>>p>>q>>r;

            cout<<(p+q+r)-max({p,q,r})<<endl;

  }
  
  




Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;

template<class T> inline void chmin(T& a, T b) {
    if (a > b) {
        a = b;
    }
}

template<class T> inline void chmax(T& a, T b) {
    if (a < b) {
        a = b;
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    vector<int> N(S.size());
    REP(i,S.size()){
        N[i] = S[i] - '0';
    }
    int ans = INT32_MAX;
    REP(i,S.size()-2)ans = min(abs(753 - (N[i]*100 + N[i + 1] * 10 + N[i + 2])),ans);
    cout <<ans<< "\n";
}

Measured memory_bytes: 256
# util functions

# debug
$debugFlag = ( ARGV[0] != nil )
p "==== DEBUG MODE ====" if $debugFlag

def pd(str)
  p str if $debugFlag
end

def printd(str)
  print str if $debugFlag
end

# input
inputs = []
lc = 0
while l = $stdin.gets do
  if false
    inputs << l.chomp.split(" ").map(&:to_s)
  else
    inputs << l.chomp.split(" ").map(&:to_i)
  end
  lc += 1
end

aa = inputs[0][0]
bb = inputs[0][1]

if aa % 2 == 0 or bb % 2 == 0
  puts "No"
else
  puts "Yes"
end

# input check
if $debugFlag
  p "--- INPUT (begin) ---"
  inputs.each do |l_i|
    p l_i
  end
  p "--- INPUT (end) ---"
  print "\n"
end

# body
if $debugFlag
end


Measured memory_bytes: 1788
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <fstream>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string toStr(T x) { ostringstream sout; sout << x; return sout.str();}
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-12;
const double PI = acos(-1.0);
const int INF = INT_MAX/10;

int main() {
	int N;
	while(cin >> N, N) {
		vi guyT(N), guyL(N);
		int M, L, S, E;
		REP(i, N) {
			cin >> M >> guyL[i];
			REP(j, M) {
				cin >> S >> E;
				FOR(k, S-6, E-6-1) {
					guyT[i] += (1<<k);
				}
			}
		}

		int ans = 0;
		vi dp(1<<16);
		REP(i, 1<<16) {
			REP(j, N) {
				if((i&guyT[j]) == 0) {
					dp[i|guyT[j]] = max(dp[i|guyT[j]], dp[i]+guyL[j]);
					ans = max(ans, dp[i|guyT[j]]);
				}
			}
		}

		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 1452
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std;
ll n;
ll a[100000][4],dp[100000][4];
 
ll f(ll day,ll flag)
{
  	if(day==n)
        return 0;
    if(dp[day][flag]!=-1)
        return dp[day][flag];
    ll maxi=0;
    if(flag==0)
    {
        maxi=max(maxi,a[day][1]+f(day+1,1));
        maxi=max(maxi,a[day][2]+f(day+1,2));
        maxi=max(maxi,a[day][3]+f(day+1,3));
    }
    else if(flag==1)
    {
        maxi=max(maxi,a[day][2]+f(day+1,2));
        maxi=max(maxi,a[day][3]+f(day+1,3));
    }
    else if(flag==2)
    {
        maxi=max(maxi,a[day][1]+f(day+1,1));
        maxi=max(maxi,a[day][3]+f(day+1,3));
    }
    else
    {
        maxi=max(maxi,a[day][1]+f(day+1,1));
        maxi=max(maxi,a[day][2]+f(day+1,2));
    }
    return dp[day][flag]=maxi;
}
 
int main() {
    cin>>n;
    for(ll i=0;i<n;i++)
        for(ll j=1;j<=3;j++)
            cin>>a[i][j];
    memset(dp,-1,sizeof(dp));
    cout<<f(0,0);
	return 0;
}

Measured memory_bytes: 17560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5, mod = 1e9 + 9;
int sd[6], isd[6];
int n, res[6];
char s[maxn + 10];
map<ll, int> mp;
ll ans;

int fpow(int x, int y) {
	int ans = 1;
	while (y) {
		if (y & 1) ans = 1ll * ans * x % mod;
		y >>= 1; x = 1ll * x * x % mod;
	}
	return ans;
}

struct data {
	int k[6], b[6];

	ll getans() {
		ll x = 0, y = 0;
		for (int i = 0; i < 6; ++i) {
			int w = 1ll * (res[i] - b[i] + mod) * fpow(k[i], mod - 2) % mod;
			if (i < 3)
				(x += 1ll * w * (i + 1) % mod) %= mod;
			else
				(y += 1ll * w * (i + 1) % mod) %= mod;
		}
		return x | (y << 32ll);
	}

	ll hsh() {
		ll x = 0, y = 0;
		for (int i = 0; i < 6; ++i) {
			if (i < 3) 
				(x += 1ll * b[i] * (i + 1) % mod) %= mod;
			else 
				(y += 1ll * b[i] * (i + 1) % mod) %= mod;
		}
		return x | (y << 32ll);
	}

	void init() {
		for (int i = 0; i < 6; ++i) {
			k[i] = 1; b[i] = 0;
		}
	}

}s1[maxn + 10], s2[maxn + 10];

data operator + (const data &a, const data &b) {
	data ans;
	for (int i = 0; i < 6; ++i) {
		ans.k[i] = 1ll * a.k[i] * b.k[i] % mod;
		ans.b[i] = (b.b[i] + 1ll * a.b[i] * b.k[i]) % mod;
	}
	return ans;
}

data inv(const data &a) {
	data ans;
	for (int i = 0; i < 6; ++i) {
		ans.k[i] = fpow(a.k[i], mod - 2);
		ans.b[i] = (mod - 1ll * ans.k[i] * a.b[i] % mod) % mod;
	}
	return ans;
}

int main() {
	scanf("%d", &n);
	scanf("%s", s + 1);
	for (int i = 0; i < 6; ++i) {
		sd[i] = rand() % mod;
		isd[i] = fpow(sd[i], mod - 2);
	}
	s1[0].init(); s2[0].init();
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < 6; ++j)
			if (s[i] == '+') {
				s1[i].k[j] = 1;
				s1[i].b[j] = 1;
			} else if (s[i] == '-') {
				s1[i].k[j] = 1;
				s1[i].b[j] = mod - 1;
			} else if (s[i] == '>') {
				s1[i].k[j] = sd[j];
				s1[i].b[j] = 0;
			} else if (s[i] == '<') {
				s1[i].k[j] = isd[j];
				s1[i].b[j] = 0;
			}
		s2[i] = inv(s1[i]);
		s1[i] = s1[i] + s1[i - 1];
		s2[i] = s2[i - 1] + s2[i];
	}
	for (int i = 0; i < 6; ++i) res[i] = s1[n].b[i];
	for (int i = 1; i <= n; ++i) {
		++mp[s2[i - 1].getans()];
		ans += mp[s1[i].hsh()];
	}
	printf("%lld", ans);
}


Measured memory_bytes: 58368
import math
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input


class FenwickTree:
    def __init__(self, a_list, f, default):
        # 0-indexed
        self.N = len(a_list)
        self.bit = a_list[:]
        self.f = f
        self.default = default
        for _ in range(self.N, 1 << int(math.ceil(math.log(self.N, 2)))):
            self.bit.append(self.default)
        for i in range(self.N - 1):
            self.bit[i | (i + 1)] = self.f(self.bit[i | (i + 1)], self.bit[i])

    def update(self, i, val):
        while i < self.N:
            self.bit[i] = self.f(self.bit[i], val)
            i |= i + 1

    def query(self, n):
        # [0, n]
        ret = 0
        while n >= 0:
            ret = self.f(ret, self.bit[n])
            n = (n & (n + 1)) - 1
        return ret


N = int(input())
X = [int(x) for x in input().split()]
dp = FenwickTree([0] * N, lambda x, y: max(x, y), 0)
for x, i in sorted((x, i) for i, x in enumerate(X)):
    dp.update(i, dp.query(i) + x)
print(N * (N + 1) // 2 - dp.query(N - 1))

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

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

ll calcNumOfCombination(ll n, ll r) {
    ll num = 1;
    for (ll i = 1; i <= r; i++) {
        num = num * (n - i + 1) / i;
    }
    return num;
}

int gcd(int x, int y) { return (x % y) ? gcd(y, x % y) : y; }

int findSumDigits(int s) {
    int num = 0;
    int temp = 0;
    while (s) {
        temp = s % 10;
        num += temp;
        s = s / 10;
    }
    return num;
}

int main() {
    int k, n;
    cin >> k >> n;
    int maxDif = 0;
    int dif = 0;
    int a[n];
    rep(i, n, 0) {
        cin >> a[i];
        if (i != 0) {
            dif = a[i] - a[i - 1];
            if (dif >= maxDif) {
                maxDif = dif;
            }
        }
    }

    dif = (k - a[n - 1]) + a[0];
    if (dif >= maxDif) {
        maxDif = dif;
    }

    int ans = k - maxDif;

    cout << ans << endl;

    return 0;
}

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

int main(){
  int K,N;cin >> K >> N;
  vector<int> A(N,0);
  for(int i=0;i<N;i++){
    cin >> A[i];
  }
  int d=A[0]-A[N-1]+K;
  for(int i=1;i<N;i++){
    d = max(d,A[i]-A[i-1]);
  }
  cout << K - d << endl;
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<algorithm>
#define max(a,b) ((a)>(b) ? (a):(b))
#define min(a,b) ((a)<=(b) ? (a):(b))
using namespace std;
using ll = long long;

int main(){
  int H,W,N;
  cin >> H >> W >> N;
  int sqCnt(0),opCnt(0);
  while(N > sqCnt){
    if(opCnt <= min(H,W))
      sqCnt += max(H,W);
    else
      sqCnt += min(H,W);
    opCnt += 1;
  }
  cout << opCnt;
  return 0;
}


Measured memory_bytes: 256
n,k = map(int,input().split())
p = list(map(int,input().split()))

sum_acc = [0]
tmp = 0
 
for i in range(n):
  tmp += (1 + p[i]) / 2
  sum_acc.append(tmp)

ans = 0
for j in range(k, n + 1): 
  ans = max(sum_acc[j] - sum_acc[j - k], ans)

print(ans)

Measured memory_bytes: 25060
// AOJ 1308 Awkward Lights
// 2018.3.8 bal4u

#include <stdio.h>
#include <string.h>

//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0;
	int c = getchar_unlocked();
	do n = (n<<3)+(n<<1) + (c & 0xf), c = getchar_unlocked();
	while (c >= '0');
	return n;
}

int inbit()
{
	int c = getchar_unlocked();
	getchar_unlocked();
	return c & 1;
}

#define N 630

// solve A X = C
//char A[N][N], X[N], C[N];
char B[N][N];				// working

int gauss_jordan(int n)
{
	int i, j, k, t, pivot;

//	for (i = 0; i < n; i++) for (j = 0; j < n; j++) B[i][j] = A[i][j];
//	for (i = 0; i < n; i++) B[i][n] = C[i];

	for (i = 0; i < n; i++) {
		pivot = -1;
		for (j = i; j < n; j++) if (B[j][i]) { pivot = j; break; }
		if (pivot < 0) continue;

		for (j = 0; j <= n; j++) {					// swap(B[i],B[pivot]);
			t = B[i][j], B[i][j] = B[pivot][j], B[pivot][j] = t;
		}

		for (j = 0; j < n; j++) if (i != j && B[j][i]) {
	        for (k = i; k <= n; k++) B[j][k] = (B[i][k] + B[j][k]) & 1;
		}
	}

	for (i = 0; i < n; i++) {
//		X[i] = B[i][n];
		if (!B[i][i] && B[i][n]) return 0;
	}
	return 1;
}

#define ABS(a)	((a)>=0?(a):-(a))
#define ID(r,c)	((r)*m+(c))

int main()
{
	int m, n, mn, d, i, j, r, c;

	while (m = in()) {
		n = in(), d = in(), mn = m*n;
		memset(B, 0, sizeof(B));

		for (i = 0; i < n; i++) for (j = 0; j < m; j++) {
			if (inbit()) B[ID(i,j)][mn] = 1;
			for (r = 0; r < n; r++) for (c = 0; c < m; c++) {
				if (r == i && c == j || ABS(r-i)+ABS(c-j) == d)
					B[ID(i,j)][ID(r,c)] = 1;
			}
		}
		putchar('0' + gauss_jordan(mn)), putchar('\n');
	}
	return 0;
}


Measured memory_bytes: 2100
#include <cstdio>

int a[10010];
int map[110][110];

int h, w, n;

void draw(int num, int color) {
    int row = num / w;
    int col = num % w;
    if (row % 2 == 1) {
        col = w - 1 - col;
    }
    map[row][col] = color;
}

int main() {
    scanf("%d", &h);
    scanf("%d", &w);
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    int cur = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < a[i]; j++) {
            draw(cur, i + 1);
            cur++;
        }
    }

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (j == w - 1) {
                printf("%d", map[i][j]);
            } else {
                printf("%d ", map[i][j]);
            }
        }
        printf("\n");
    }
}


Measured memory_bytes: 256
#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <functional>
#include <iomanip>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)

int main() {
	
	int n;
	double sum = 0.0;
	int cnt = 0;
	cin >> n;
	vector<vector<int>> town(n, vector<int>(2));
	rep(i, n) {
		cin >> town.at(i).at(0);
		cin >> town.at(i).at(1);
	}
	vector<int> indexes(n);
	rep(i, n) indexes[i] = i;

	
	do {
		rep(i, n - 1) {
			int k = indexes.at(i);
			int l = indexes.at(i + 1);
			int xi = town.at(k).at(0);
			int yi = town.at(k).at(1);
			int xj = town.at(l).at(0);
			int yj = town.at(l).at(1);
			double x = pow(xi - xj, 2.0);
			double y = pow(yi - yj, 2.0);
			sum += sqrtf(x + y);
		}
		cnt++;

	} while (next_permutation(indexes.begin(), indexes.end()));

	double ave = sum / cnt;

	printf("%lf", ave);

}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<vector>
#include<queue>
#include<deque>
using namespace std;
typedef pair<int, int>P;
typedef pair<int, pair<int, int>>PP;
typedef long long ll;

int main() {
	int n, k; cin >> n >> k;
	int v[100];
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	int l[100];
	fill(l, l + 100, 0);
	int ans = 0;
	for (int a = 0; a <= n; a++) {
		for (int b = 0; b <= min(k-a,n-a); b++) {
			int have = 0;
			int index = 0;
			for (int i = 0; i < a; i++) {
				have += v[i];
				l[index] = v[i];
				index++;
			}
			for (int i = n - 1; i >= n - b; i--) {
				have += v[i];
				l[index] = v[i];
				index++;
			}
			sort(l, l + index);
			for (int i = 0; i < min(index,k - a - b); i++) {
				if (l[i] < 0) {
					have -= l[i];
				}
			}
			ans = max(ans, have);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
//
//  main.c
//  ITP1_2_A Small, Large, or Equal
//
//  Created by x17054xx on 2017/04/28.
//  Copyright ?? 2017??´ x17054xx. All rights reserved.
//

#include <stdio.h>

int main(int argc, const char * argv[]) {
    int a, b;
    scanf("%d %d",&a,&b);
    
    if(a<b){
        printf("a < b\n");
    }else if(a>b){
        printf("a > b\n");
    }else{
        printf("a == b\n");
    }
    
    
    return 0;
}

Measured memory_bytes: 580
#include <cstdio>
using namespace std;
int main(void)
{
  int a,b,ball[10],n,i,flag;
  scanf("%d",&n);
  while(n-->0)
  {
    a=-1;b=-1;
    for(i=0;i<10;i++)
      scanf("%d",&ball[i]);
    for(i=0;i<10;i++)
    {
      flag=0;
      if(ball[i]>a)
        flag=1;

      if(ball[i]>b)
      {
        if(flag==1)
        {
          if(ball[i]-a<ball[i]-b)
            a=ball[i];
          else
            b=ball[i];
        }else{
          b=ball[i];
        }
        flag=2;
      }
      if(flag==0)
      {
        printf("NO\n");
        break;
      }
      if(flag==1)
        a=ball[i];
    }
    if(flag!=0)
      printf("YES\n");
  }
  return 0;
}

Measured memory_bytes: 1008