akhauriyash/Code-Regression huggingface dataset:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    H,W = LI()
    A = [LI() for _ in range(H)]
    B = [LI() for _ in range(H)]
    C = [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            C[i][j] = abs(A[i][j] - B[i][j])
    D = [[set() for _ in range(W+1)] for _ in range(H+1)]
    D[0][1] = {0}
    for i in range(1,H+1):
        for j in range(1,W+1):
            for k in D[i-1][j] | D[i][j-1]:
                D[i][j].add(abs(k+C[i-1][j-1]))
                D[i][j].add(abs(k-C[i-1][j-1]))

    print(min(D[-1][-1]))


if __name__ == '__main__':
    main()

Measured memory_bytes: 551612
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef int Def;
//typedef ll Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
//#define mt make_tuple
//typedef tuple<int,int,int> tp;
//typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
	int n;
	cin>>n;
	vi in(n);
	rep(i,n)cin>>in[i];
	sort(all(in));
	int t=in[n-1];
	int r=0;
	rep(i,n-1)if(abs(r-t/2)>abs(in[i]-t%2-t/2))r=in[i];
	cout<<t<<" "<<r<<endl;
}






Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define fast_input ios_base::sync_with_stdio(false);cin.tie(NULL);
typedef long long int ll;
int main()
{
    fast_input;
    int k,x;
    cin>>k;
    cin>>x;
    if(500*k>=x)
      cout<<"Yes"<<endl;
    else
      cout<<"No"<<endl;
}

Measured memory_bytes: 256
//060
#include <bits/stdc++.h>
#define rep(i,n) for(int i=1; i<=n; i++)
using namespace std;
int main(void){
    int a,b,c,d;
    int i=0;
    vector<int>L;
    cin>> a >> b >> c;
    while (true){ //回数が分からないのでwhile
        i+=1;
        d = a*i%b;
        if(d==c){
            cout << "YES" << endl;
            return 0;
        }
        auto itr = find(L.begin(), L.end(), d);
        if (itr ==L.end()){
            L.push_back(d);
        }else{
            cout << "NO" << endl;
            return 0;
        }
    }
}

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}
ll nextLong() { ll x; scanf("%lld", &x); return x;}

int main2() {
  int K = nextInt();
  int A = nextInt();
  int B = nextInt();

  bool ans = 0;
  for (int i = A; i <= B; i++) {
    if (i % K == 0) {
      ans = true;
    }
  }
  cout << (ans ? "OK" : "NG") << endl;
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}

Measured memory_bytes: 3764
results = []
while true do
   n, x = gets.split.map(&:to_i)
   if n == 0 && x == 0
      break
   end
   nums = []
   (1..n).each do |i|
      nums << i
   end
   sum = 0
   nums.combination(3) do |a,b,c|
      if a + b + c == x
         sum +=1
      end
   end
   results << sum
end

results.each do |result|
   puts result
end

Measured memory_bytes: 8744
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>

using namespace std;
typedef long long ll;
 
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep_r(i,n) for(int i=((int)(n)-1);i>=0;--i)
#define FOR(i,m,n) for(int i=((int)(m));i<(int)(n);++i)
#define FOR_R(i,m,n) for(int i=((int)(m)-1);i>=(int)(n);--i)
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vp vector<pii>
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define INF 1e9
#define LLINF 1e18
#define PI (acos(-1))
#define MOD 1e9+7

int main(){
	int n;
	cin >> n;
	
	vi v(n + 1);
	FOR(i, 1, n + 1)
		cin >> v[i];
	
	int a = v[1], ans = 0;
	
	rep(i, n){
		if(a == 2){
			cout <<ans + 1<<endl;
			break;
		}
		a = v[a];
		ans++;
		
	}
	
	if(a != 2) cout << -1 << endl;
	
	return 0;
}
	

Measured memory_bytes: 640
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
#define ll long long
#define pi (acos(-1))
int main()


{   
    int n,a;
    std::cin >> n;
    std::cin >> a;
    int l=a;
   int r=a+n-1; 
   int s=0;
    if (r <= 0) { s = r; }
    else if (l >= 0)
    {
        s = l;
    }
    int sum = 0;
    for (int i = 1; i <= n; ++i) { sum += (i + l - 1); }
  
    std::cout << sum - s << std::endl;
    return 0;
} 


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
double s;
long long n;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i = 1;i <= 50000; i++){
         s = i*1.08;
        int q=(int)s;
        if(n==q){
            cout<<i<<endl;
            return 0;
        }
    }
    cout << ":(" << endl;
return 0;}



Measured memory_bytes: 3628
#include<iostream>
using namespace std;
int main(){
	
	int h,w;
	string a[102];
	cin>>h>>w;
	for(int i=0;i<h;i++)cin>>a[i];
	for(int i=0;i<w+2;i++)cout<<"#";
	cout<<endl;
	for(int i=0;i<h;i++)cout<<"#"<<a[i]<<"#"<<endl;
	for(int i=0;i<w+2;i++)cout<<"#";
	cout<<endl;
	
	
	return 0;

}

Measured memory_bytes: 256
N=int(input())
a=list(map(int, input().split()))
x=a[0]
y=sum(a)-a[0]
out=abs(x-y)
for i in range(1, N-1):
  x+=a[i]
  y-=a[i]
  if abs(x-y)<out:
    out=abs(x-y)
print(out)

Measured memory_bytes: 23800
# N = int(input())

import numpy as np

N,M,X = list(map(int, input().split()))
prices = []
As = np.zeros((N,M+1), dtype=int)

for i in range(N):
    As[i] = np.array(list(map(int, input().split())))

queue = []

def f(id, price, skill):
    # print(skill.min())
    
    if skill.min()>=X:
        # print("here")
        return price
    else:
        if id >= N:
            return np.inf
        else:
            return min(f(id+1, price+As[id,0], skill + As[id, 1:]), f(id+1, price, skill))

ans = f(0,0,np.zeros(M))
if ans == np.inf:
    print(-1)
else:
    print(ans)


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

  int n,x,i,j,k;
  int count;
 
  scanf("%d",&n);
  scanf("%d",&x);
  while (!((n==0) && (x==0))){
    count=0;
    for (i=1;i<=n;i++){
      for (j=1;j<=n;j++){
        for (k=1;k<=n;k++){
          if (!((i==j) || (i==k) || (j==k))){
            if (i+j+k==x){
              count++;
 
            }
          }
        }
      }
    }
    printf("%d\n",count/6);
    scanf("%d",&n);
    scanf("%d",&x);
  }
 
  return 0;
}


Measured memory_bytes: 2056
from random import randint

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

for i in range(D):
    l = S[i].index(max(S[i]))
    T.append(l+1)
    
print(*T, sep="\n")

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

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int M = 0;
		int cnt=(N-1)*(N-2)/2-K;
		if (cnt<0) {
			System.out.println(-1);
		} else {
			System.out.println((N-1)*(N-2)/2-K+(N-1));
			for (int i=2;i<=N;i++) {
				System.out.println(1 + " " + i);
				M++;
			}
			for (int i=2;i<=N;i++) {
				for (int j=i+1;j<=N;j++) {
					if (cnt>0) {
						System.out.println(i + " " + j);
						M++;
					}
					if (cnt==0) {
						break;
					}
					cnt--;
				}
			}
		}
	}
}

Measured memory_bytes: 23764
#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<iostream>
#define pb push_back
#define fi first
#define se second
#define sz(x)  x.size()
#define cl(x)  x.clear()
#define all(x)  x.begin() , x.end()
#define r(x)  scanf("%d", &x)
#define rr(x , y)  scanf("%d%d" , &x , &y)
#define rst(s)  scanf("%s" , s)
#define rl(x)  scanf("%lld" , &x)
#define rrl(x , y)  scanf("%lld%lld" , &x , &y)
#define w(x)  printf("%d" , x)
#define ww(x , y)  printf("%d %d" , x , y)
#define wl(x)  printf("%lld" , x)
#define wwl(x , y)  printf("%lld %lld" , x , y)
#define sp()  printf(" ")
#define en()  puts("")
#define rep(i , x , n)  for(int i = x ; i <= n ; i ++)
#define per(i , n , x)  for(int i = n ; i >= x ; i --)
#define mem0(x)  memset(x , 0 , sizeof(x))
#define mem_1(x)  memset(x , -1 , sizeof(x))
#define mem_inf(x)  memset(x , inf , sizeof(x))
#define mem__inf(x)  memset(x , -inf , sizeof(x))
#define p_queue priority_queue
#define debug(x)  cout << '*' << x << '\n'
#define ddebug(x , y)  cout << '*' << x << ' ' << y << '\n'
#define ios std::ios::sync_with_stdio(false) , cin.tie(0)
using namespace std ;
//mt19937  rnd(chrono::high_resolution_clock::now().time_since_epoch().count()) ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair<int , int> pii ;
typedef pair<ll , ll> pll ;
typedef pair<int , ll> pil ;
typedef pair<ll , int> pli ;
typedef pair<double , double> pdd ;
const int inf = 0x3f3f3f3f ;
const ll mod = 1e9 + 7 ;
const int maxn = 4e4 + 5 ;
const int maxm = 30 ;
const double eps = 1e-6 ;
const double pi = acos(-1.0) ;
int main()
{
	char s[5] ;
	rst(s) ;
	if(s[1] == 'B')  puts("ARC") ;
	else  puts("ABC") ;
}

Measured memory_bytes: 3760
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
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());
  
  if( N == 2){ cout << A[1] << " " << A[0] << endl; return 0;}
  
  int n = A.back();
  if(n%2 == 0){ 
    int itr1 = lower_bound(A.begin(),A.end(),n/2) - A.begin();
    int itr2 = upper_bound(A.begin(),A.end(),n/2) - A.begin();
    itr2--;
    if(abs(A[itr1]-n/2) >abs(A[itr2]-n/2)){ itr1 = itr2;}
    cout << A.back() << " " << A[itr1] << endl; return 0;}
  else{
    int itr1 = lower_bound(A.begin(),A.end(),n/2) - A.begin();
    int itr2 = upper_bound(A.begin(),A.end(),n/2) - A.begin();
    int itr3 = lower_bound(A.begin(),A.end(),(n+1)/2) - A.begin();
    int itr4 = upper_bound(A.begin(),A.end(),(n+1)/2) - A.begin();
    itr2--; itr4--;
    if(abs(A[itr1]-n/2) > abs(A[itr2]-n/2)){ itr1 = itr2;}
    if(abs(A[itr3]-(n+1)/2) > abs(A[itr4]-(n+1)/2)){ itr3 = itr4;}
    if(abs(A[itr1]-n/2) >= abs(A[itr3]-(n+1)/2)){ itr1 = itr3;}
    
    cout << A.back() << " " << A[itr1] << endl; return 0;}
}
           
                                
         
                              

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

int main(){
	int N;
	cin >> N;
	vector<int> A(N+2);
	REP(i, N) cin >> A[i+1];
	A[0] = 0;
	A[N+1] = 0;
	ll total = 0;
	REP(i, N+1) total += abs(A[i+1]-A[i]);
	REP(i, N){
		int a = A[i+1] - A[i];
		int b = A[i+2] - A[i+1];
		if(a*b>=0){
			cout << total << endl;
		}else{
			cout << total - abs(a) - abs(b) + abs(a+b) << endl;
		}
	}
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;

double A, B, C, D, E, F;

int main(void){
    
    scanf("%lf %lf %lf %lf %lf %lf", &A, &B, &C, &D, &E, &F);
    
    int a = 100 * A, b = 100 * B;
    
    vector<double> water;
    for(int i = 0; i < F; i += a){
        for(int j = 0; i + j < F; j += b){
            if(i + j == 0) continue;
            water.push_back(i + j);
        }
    }
    sort(water.begin(), water.end());
    
    vector<double> sugar;
    for(int i = 0; i < F; i += C){
        for(int j = 0; i + j < F; j += D){
            sugar.push_back(i + j);
        }
    }
    sort(sugar.begin(), sugar.end(), greater<double>());
    
    double Q = E / 100;
    pair<double, double> ans = make_pair(0, 0);
    for(int i = 0; i < water.size(); ++i){
        for(int j = 0; j < sugar.size(); ++j){
            if(water[i] + sugar[j] <= F && sugar[j] / water[i] <= Q){
                double a = (ans.second == 0) ? 0 : (100 * ans.second) / (ans.first + ans.second), b = (sugar[j] == 0) ? 0 : (100 * sugar[j]) / (water[i] + sugar[j]);
                if(a <= b) ans = make_pair(water[i], sugar[j]);
            }
        }
    }
    printf("%.f %.f\n", ans.first + ans.second, ans.second);
    
    return 0;
}


Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  
  int A = N / 1000;
  int B = (N % 1000) / 100;
  int C = (N % 100) / 10;
  int D = N % 10;
 
  if ( B == C && (A == B || C == D) ) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3604
#include <iostream>
#include <vector>
#include <string>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <climits>
#include <iomanip>
#include <deque>

using namespace std;

int main()
{
  int W, H, x, y, r;

  cin >> W >> H >> x >> y >> r;

  if (0 <= x - r && x + r <= W && 0 <= y - r && y + r <= H) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }

  return 0;
}



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

int main(){
    int n,m;
    cin >> n >> m;
    vector<vector<int>> tasks(m + 1, vector<int>(0));
    
    for(int i = 0; i < n; i++){
        int a,b;
        cin >> a >> b;
        
        if(a < m + 1){
            tasks.at(a).push_back(b);
        }
    }
    
    int answer = 0;
    
    priority_queue<int> q;
    
    for(int i = 1; i < m + 1; i++){
        for(int j = 0; j < tasks.at(i).size(); j++){
            q.push(tasks.at(i).at(j));
        }
        
        if(q.size() != 0){
            answer += q.top();
            q.pop();
        }

        
    }
    
    cout << answer << endl;
    
}

Measured memory_bytes: 5504
from collections import deque
from enum import Enum
import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

class Node:
    def __init__(self):
        self.parent_id = -1
        self.depth = 0
        self.children = []

global nodes

def calc_depth(node_id,arg_depth):

    nodes[node_id].depth = arg_depth
    for child in nodes[node_id].children:
        calc_depth(child, arg_depth+1)


V = int(input())

nodes = []
#あらかじめ、V個のノードを用意しておく
for loop in range(V):
    node = Node()
    nodes.append(node)

#親子関係の取得
for loop in range(V):

    table = list(map(int,input().split()))
    node_id = table[0]
    num = table[1]

    for i in range(num):
        child_id = table[2+i]
        nodes[node_id].children.append(child_id)
        nodes[child_id].parent_id = node_id


#根を探して、深さを計算する
for i in range(V):
    if nodes[i].parent_id == -1:
        calc_depth(i,0)
        break


for i in range(V):

    print("node %d: parent = %d, depth = %d, "%(i,nodes[i].parent_id,nodes[i].depth),end = "")

    if nodes[i].parent_id == -1:
        print("root,",end = "")
    else:
        if len(nodes[i].children) == 0: #葉
            print("leaf,",end = "")
        else: #節
            print("internal node,",end = "")

    print(" [",end = "")
    print(', '.join(map(str,nodes[i].children)),end = "")
    print("]")





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

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    if(n%2==1){
        cout << "No" << endl;
        return 0;
    }
    rep(i, n/2){
        if(s.at(i) != s.at(n/2+i)){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<queue>
#include<cstdio>

#define inf 1000000000

using namespace std;

class sint{
	public:
	int iti,now;
	sint(){}
	sint(int a,int b){iti=a;now=b;}
	bool operator < (const sint &a) const{
		return now>a.now;
	}
};

int n,m;
int road[21][21];
int dike(int st,int en){
	priority_queue<sint> state;
	int sima[101];
	int visit[101];
	
	for(int i=0;i<101;i++){
		sima[i]=inf;
		visit[i]=0;
	}
	
	state.push(sint(st,0));
	sima[st]=0;
	
	while(1){
		sint u = state.top();
		state.pop();
		/*
		for(int i=1;i<=n;i++){
			printf("%d ",sima[i]);
		}puts("");
		
		printf("now = %d en = %d\n",u.iti,en);
		*/visit[u.iti]=1;
		
		if(u.iti==en){
			return u.now;
		}
		
		for(int i=1;i<=n;i++){
			if(road[u.iti][i]==inf||visit[i]==1)continue;
			if(sima[u.iti]+road[u.iti][i]<sima[i]){
				sima[i]=sima[u.iti]+road[u.iti][i];
				state.push(sint(i,sima[i]));
			}
		}
	}
}

int main(){
	cin>>n>>m;
	for(int i=0;i<21;i++){
		for(int j=0;j<21;j++){
			road[i][j]=inf;
		}
	}
	
	for(int i=0;i<m;i++){
		int a,b,c,d;
		scanf("%d,%d,%d,%d",&a,&b,&c,&d);
		road[a][b]=c;
		road[b][a]=d;
	}
	
	int st,en,d1,d2;
	scanf("%d,%d,%d,%d",&st,&en,&d1,&d2);
	
	int gou = dike(st,en);
	gou+=dike(en,st);
	
	printf("%d\n",d1-d2-gou);
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define M 1000000007
using namespace std;

int dp[10005][2][2];

void DP(string A, string B, string C){
  
  while(A.size()<B.size()) A='0'+A;
  
  int ans=0;
  
  for(int i=0;i<A.size();i++){
    
    if(i+C.size()-1>=A.size()) break;
    
    memset(dp,0,sizeof(dp));
    
    for(int j=A[0];j<=B[0];j++){
      int a=1, b=1;
      if(j==A[0]) a=0;
      if(j==B[0]) b=0;
      if(!i){
	a=1, b=1;
	if(C[0]==A[0]) a=0;
	if(C[0]==B[0]) b=0;
	if(C[0]<A[0]) continue;
	if(B[0]<C[0]) continue;
	dp[1][a][b]++;
	break;
      }
      dp[1][a][b]++;
    }
    
    for(int j=1;j<A.size();j++){
      
      for(int k=0;k<2;k++){
	for(int l=0;l<2;l++){
	  
	  if(!dp[j][k][l]) continue;
	  
	  for(int num='0';num<='9';num++){
	    
	    if(i<=j&&j<=i+C.size()-1){
	      num=C[j-i];
	      if(k==0&&num<A[j]) break;
	      if(l==0&&num>B[j]) break;
	    }
	    
	    if(k==0&&num<A[j]) continue;
	    if(l==0&&num>B[j]) continue;
	    
	    int nk=k, nl=l;
	    if(!nk&&A[j]<num) nk=1;
	    if(!nl&&B[j]>num) nl=1;
	    
	    dp[j+1][nk][nl]=(dp[j+1][nk][nl]+dp[j][k][l])%M;
	    
	    if(i<=j&&j<=i+C.size()-1) break;
	  }
	  
	}
      }
      
    }
    
    for(int j=0;j<2;j++)
      for(int k=0;k<2;k++) ans=(ans+dp[A.size()][j][k])%M;
    
  }
  
  cout<<ans<<endl;
}

int dp2[10005][2][2][2];

void DP2(string A, string B, string C){
  
  int ans=0;
  
  if(A=="0") ans=1;
  
  while(A.size()<B.size()) A='0'+A;
  
  for(int i=1;i<A.size();i++){
    
    memset(dp2,0,sizeof(dp2));
    
    for(int j=A[0];j<=B[0];j++){
      int a=1, b=1;
      if(j==A[0]) a=0;
      if(j==B[0]) b=0;
      if(j=='0') dp2[1][a][b][0]++;
      else dp2[1][a][b][1]++;
    }
    
    for(int j=1;j<A.size();j++){
      
      for(int k=0;k<2;k++)
	
	for(int l=0;l<2;l++){
	  
	  for(int m=0;m<2;m++){
	    
	    if(!dp2[j][k][l][m]) continue;
	    
	    if(j==i){
	      
	      int nk=k, nl=l;
	      
	      if( nk == 0 && '0' < A[j] ) continue;
	      if( nl == 0 && '0' < B[j] ) nl=1;
	      
	      dp2[j+1][nk][nl][m]=(dp2[j+1][nk][nl][m]+dp2[j][k][l][m])%M;
	      
	    }else{
	      
	      for(int num='0';num<='9';num++){
		
		int nk=k, nl=l;
		
		if( nk == 0 && num < A[j] ) continue;
		if( nl == 0 && B[j] < num ) continue;
		
		if( nk == 0 && A[j] < num ) nk=1;
		if( nl == 0 && num < B[j] ) nl=1;
		
		if(m==0){
		  
		  if(num=='0') dp2[j+1][nk][nl][0]=(dp2[j+1][nk][nl][0]+dp2[j][k][l][0])%M;
		  else if(j<=i) dp2[j+1][nk][nl][1]=(dp2[j+1][nk][nl][1]+dp2[j][k][l][0])%M;
		  
		}
		else dp2[j+1][nk][nl][1]=(dp2[j+1][nk][nl][1]+dp2[j][k][l][1])%M;
		
	      }
	      
	    }
	    
	  }
	}
      
    }
    
    for(int j=0;j<2;j++)
      for(int k=0;k<2;k++) ans=(ans+dp2[A.size()][j][k][1])%M;
    
  }
  
  cout<<ans<<endl;
}

string A, B, C;

int main(){

  cin>>A>>B>>C;

  if(C=="0") DP2(A, B, C);
  
  else DP(A, B, C);
    
  return 0;
}

Measured memory_bytes: 3512
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
int main(){
	int N;
	scanf("%d",&N);
	vector<long long>v(N+1);
	for(int i=1;i<=N;i++)scanf("%lld",&v[i]);
	sort(v.begin()+1,v.end());
	vector<long long>w(N+1);
	for(int i=1;i<=N;i++)w[i]=w[i-1]+v[i];
	int M;
	scanf("%d",&M);
	vector<long long>p(M);
	for(int i=0;i<M;i++){
		long long x;
		scanf("%lld",&x);
		auto it=upper_bound(v.begin(),v.end(),x);
		p[i]=w[distance(v.begin(),--it)];
	}
	for(int i=0;i<M;i++){
		long long x;
		scanf("%lld",&x);
		puts(p[i]>=x?"Yes":"No");
	}
}

Measured memory_bytes: 7792
#[allow(unused_imports)]
use proconio::{fastout, input, marker::*};

#[fastout]
fn main() {
   input! {
      n: usize,
      k: usize,
      mut p: [usize; n]
   }
   p.sort();
   let mut ans = 0;
   for i in 0..k {
      ans += p[i];
   }
   println!("{}", ans);
}


Measured memory_bytes: 2216
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <numeric>
#include <climits>
#define M 1000000007
#define ll long long
#define LIM 100000
using namespace std;
ll v[LIM];
int main() {
  string a;
  cin >> a;
  if (a == "a" || a == "i" || a == "u" || a == "e" || a == "o") {
    cout << "vowel" << endl;
  } else {
    cout << "consonant" << endl;
  }
  return 0;
}


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

#define rep(i,n) for(ll i=0;i<(n);++i)
#define reps(i,n) for(ll i=1;i<=(n);++i)
using ll = long long;
using str = string;
constexpr long long INF = (1LL<<60);
constexpr long long MOD = (1e9+7);
template<class T>inline bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
inline void dump(){cout<<endl;}
template<class Head,class... Tail>inline void dump(Head&& head, Tail&&... tail){cout<<head<<", ";dump(forward<Tail>(tail)...);}
template<typename T>inline istream &operator>>(istream&input,vector<T>&v){for(auto &elemnt:v)input>>elemnt;return input;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vector(size_t a, Ts... ts){return vector<decltype(make_vector<T>(ts...))>(a, make_vector<T>(ts...));}

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

  ll n;
  cin>>n;
  vector<ll> a(n);
  cin>>a;

  sort(a.begin(),a.end());
  ll ans=0;
  rep(i,n){
    for(ll j=i+1;j<n;++j){
      ll key1=a[j];
      ll key2=a[i]+a[j];
      auto rig=lower_bound(a.begin(),a.end(),key2);
      rig--;
      ll ldx=j+1;
      ll rdx=rig-a.begin();
      if(ldx>rdx)continue;
      ans += rdx-ldx+1;
    }
  }
  cout<<(ans)<<endl;

}


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

using namespace std;
int l[100000];
int r[100000];
int came_num[100001];
int left_num[100001];
int main(){
    int N;
    int T;
    cin >> N >> T;
    for(int i = 0; i < N; i++){
        cin >> l[i] >> r[i];
    }

    sort(l, l + N);
    sort(r, r + N);
    queue <int> came_queue;
    queue <int> left_queue;
    for(int i = 0; i < N; i++){
        came_queue.push(l[i]);
        left_queue.push(r[i]);
    }
    for(int i = 0; i < T; i++){
        if(i != 0){
            came_num[i] = came_num[i - 1];
            left_num[i] = left_num[i - 1];
        }
        if(!came_queue.empty() && i == came_queue.front()){
            while(i == came_queue.front() && !came_queue.empty()){
                came_num[i] += 1;
                came_queue.pop();
            }
        }
        if(!left_queue.empty() && i == left_queue.front()){
            while(i == left_queue.front() && !left_queue.empty()){
                left_num[i] += 1;
                left_queue.pop();
            }
        }
    }

    int ans = 0;
    for(int i = 0; i < T; i++){
        ans = max(ans, came_num[i] - left_num[i]);
    }
    
    cout << ans << endl;
    /* 
    for(int i = 0; i < T; i++){
        cout << came_num[i] << " ";
    }
    cout << endl;

    for(int i = 0; i < T; i++){
        cout << left_num[i] << " ";
    }
    cout << endl;
    */
    return 0;
}



Measured memory_bytes: 5248
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = int64_t;
#define rep(i, j, n) for (int i = j; i < (int)n; ++i)
#define rrep(i, j, n) for (int i = (int)n - 1; j <= i; --i)

constexpr ll MOD = 1000000007;
constexpr int INF = 0x3f3f3f3f;

int main() {
  ll n, c, k;
  cin >> n >> c >> k;
  vector<ll> t(n);
  rep(i, 0, n) cin >> t[i];
  sort(t.begin(), t.end());

  int ans = 1;
  int cnt = 1;
  int start = t[0];
  rep(i, 1, n) {
    if (t[i] <= start + k && cnt + 1 <= c) {
      ++cnt;
    } else {
      ++ans;
      start = t[i];
      cnt = 1;
    }
  }
  cout << ans << endl;
  return 0;
}

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

int main()
{
    //input
    int N,max;
    int count = 1;
    cin >> N;
    vector<int> H(N);
    for (int i = 0; i < N; i++)
    {
        cin >> H[i];
    }
    max = H[0];
    //calc
    for (int i = 1; i < N; i++)
    {
        if(H[i]>=max){
            count++;
            max = H[i];
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int INF = 1001001001;

int main() {
int A,B;
cin >> A >> B;
int cnt = 0;
for (int i = 0;i < 2;i++) {
if (A > B) {
    cnt += A;
    A--;
} else {
    cnt += B;
    B--;
}
}
cout << cnt << endl;


return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

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

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  char a;
  cin >> a;
  
  if ( a == 'A'){
    cout << 'T' << endl;
  }
  else if ( a == 'T'){
    cout << 'A' << endl;
  }
  else if ( a == 'C'){
    cout << 'G' << endl;
  }
  else if ( a == 'G'){
    cout << 'C' << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int n, a[4] = {}, i;
    char s[4];
    
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%s", s);
        if (s[0] == 'A')
            a[0]++;
        if (s[0] == 'W')
            a[1]++;
        if (s[0] == 'T')
            a[2]++;
        if (s[0] == 'R')
            a[3]++;
    }
    printf("AC x %d\nWA x %d\nTLE x %d\nRE x %d", a[0],a[1],a[2],a[3]);
}


Measured memory_bytes: 1736
program main
      implicit none
      integer(4) :: n, m, i, cnt
      integer(8), allocatable :: h(:)
      integer(4), allocatable :: a(:), b(:)
      integer(4), allocatable :: tmp(:)

      read *, n, m
      allocate( h(n) )
      read *, h

      allocate( a(m) )
      allocate( b(m) )

      allocate( tmp(n) )
      tmp(:) = 0
      do i = 1, m
        read *, a(i), b(i)
        tmp(a(i)) = tmp(a(i)) + 1
        tmp(b(i)) = tmp(b(i)) + 1
      end do

      do i = 1, m
        if ( h(a(i)) > h(b(i)) ) then
          tmp(a(i)) = tmp(a(i)) - 1
        else if ( h(a(i)) < h(b(i)) ) then
          tmp(b(i)) = tmp(b(i)) - 1
        else if ( h(a(i)) == h(b(i)) ) then
        end if
      end do

      cnt = 0
      do i = 1, n
        if ( tmp(i) == 0 ) then
          cnt = cnt + 1
        end if
      end do

      print *, cnt

end program main


Measured memory_bytes: 4900
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define pp pair<ll,ll>
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;
ll MOD=1000000007;

 
int main() {
    int s,w;
    cin >> s >> w;
    if (w>=s) cout << "unsafe" << endl;
    else cout << "safe" << endl;
}


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

using namespace std;
const int MOD = 1e9+7;

int mul(int a,int b)
{
    return (long long) a*b % MOD;
}

int my_pow(int a,int b)
{
    int r=1;
    while(b)
    {
        if(b%2)
        {
            r=mul(r,a);
        }
        a=mul(a,a);
        b/=2;
    }
    return r;
}
int my_inv(int a)
{
    return my_pow(a,MOD-2);
}

void sub_self(int &a,int b)
{
    a-=b;
    if(a<0)
    {
        a+=MOD;
    }
}
int main() {
	// your code goes here
	int n,k;
	cin>>n>>k;
	vector<int>fac(2*n+1);
	fac[0]=1;
	for(int i=1;i<=2*n;i++)
	{
	    fac[i]=mul(fac[i-1],i);
	}
	
	auto binomial = [&](int a,int b){
	    if(a<b){
	        return 0;
	    }
	    return mul(fac[a],my_inv(mul(fac[b],fac[a-b])));
	};
	
	vector<int>a(n);
	for(int&x : a)
	{
	    cin>>x;
	}
	
	sort(a.begin(),a.end());
	int answer=0;
	for(int i=0;i<n-1;i++)
    {
        int d = (a[i+1]-a[i])%MOD;
        int ways=binomial(n,k);
        sub_self(ways,binomial(i+1,k));
        sub_self(ways,binomial(n-i-1,k));
        answer=(answer+mul(d,ways))%MOD;
    }
    cout<<answer<<endl;
	return 0;
}


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

int main() {
  int n;
  cin >> n;
  int t = 0, x = 0, y = 0;
  for (int i = 0; i < n; i++) {
    int tt, xt, yt;
    cin >> tt >> xt >> yt;
    int tm = tt - t;
    int dist = abs(x - xt) + abs(y - yt);
    if (dist > tm) {
      puts("No");
      return 0;
    } else if ((tm - dist) & 1) {
      puts("No");
      return 0;
    }
    t = tt;
    x = xt;
    y = yt;
  }
  puts("Yes");
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define RNG(i,from,to) for(int i=(from); i<(int)(to); i++)
#define gcd(i,j) __gcd((i), (j))
typedef long long ll;
typedef pair<int, int> pii;
template<typename S, typename T> string to_string(pair<S, T> p) { return "("+to_string(p.first)+","+to_string(p.second)+")"; }
template<typename T> string to_string(T p[2]) { return "["+to_string(p[0])+","+to_string(p[1])+"]"; }
template<typename T> void strprint(T e){ cout << to_string(e) << endl; }
template<typename T> void strprint(const vector<T>& v){ cout << "[";for(const auto& e : v){ cout << to_string(e) << ","; }cout << "]";cout << endl; }
template<typename T> void strprint(const vector<vector<T>>& vv){ for(const auto& v : vv){ strprint(v); } }
template<typename Iter> void strprint(Iter first, Iter last){ for(auto it=first; it != last; it++){ cout << *it << " "; }; cout << endl; }
const ll DVSR = 1e9+7;


int main(int argc, char const *argv[])
{
  ll H, W; cin >> H >> W;
  string MP[H];
  REP(i, H) {
    cin >> MP[i];
  }
  ll compH = 0, compW = 0;
  REP(i, H) {
    bool isEmpty = true;
    REP(j, W) {
      isEmpty = isEmpty && MP[i][j] == '.';
    }
    if (!isEmpty) {
      MP[compH] = MP[i];
      compH++;
    }
  }
  REP(j, W) {
    bool isEmpty = true;
    REP(i, compH) {
      isEmpty = isEmpty && MP[i][j] == '.';
    }
    if (!isEmpty) {
      REP(i, compH) {
        MP[i][compW] = MP[i][j];
      }
      compW++;
    }
  }
  REP(i,compH) {
    cout << MP[i].substr(0, compW) << endl;
  }
  return 0;
}


Measured memory_bytes: 256
S = input()
n, w = S.count('N'), S.count('W')
s, e = S.count('S'), S.count('E')
flag = True
if n == 0 or s == 0:
    if n != s:
        flag = False
if w == 0 or e == 0:
    if w != e:
        flag = False
print('Yes' if flag else 'No')


Measured memory_bytes: 3060
///Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>

#define                           int                         long long
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<int,int>
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);




using namespace std;

const int inf=1e18;
const int mod=1e9+7;
const int M=100009;
inline int bigmod(int B,int P){int R=1;while(P>0){if(P&1){R=(R*B)%mod;}P>>=1;B=(B*B)%mod;}return R;}

string s[12];
int h,w,k;
int part[13];
int solve(int msk)
{
    memset(part,0,sizeof part);
    vector<pi>vec;
    int last=1;
    for(int i=0;i<h-1;i++)
    {
        if(msk & (1LL<<i))
        {
            vec.pb(mp(last,i+1));
            last=i+2;
        }
    }
    vec.pb(mp(last,h));
    int sz=vec.size();
    int cnt=0;
    for(int j=1;j<=w;j++)
    {
        for(int p=0;p<sz;p++)
        {
            int lft=vec[p].fi;
            int rgt=vec[p].si;
            for(int i=lft;i<=rgt;i++)
            {
                if(s[i][j]=='1')
                {
                    part[p]++;
                }
            }
        }
        int mx=0;
        for(int p=0;p<sz;p++)
        {
            mx=max(mx,part[p]);
        }
        if(mx>k)
        {
            cnt++;
            memset(part,0,sizeof part);
             for(int p=0;p<sz;p++)
        {
            int lft=vec[p].fi;
            int rgt=vec[p].si;
            for(int i=lft;i<=rgt;i++)
            {
                if(s[i][j]=='1')
                {
                    part[p]++;
                }
            }
        }
        mx=0;
         for(int p=0;p<sz;p++)
        {
            mx=max(mx,part[p]);
        }
          if(mx>k)return inf;
        }
    }
    cnt=cnt+__builtin_popcountll(msk);
    return cnt;
}
 main()

{
    fast
    cin>>h>>w>>k;
    int ses=inf;
    f(i,1,h)
    {
       cin>>s[i];
       s[i]="#"+s[i];
    }
    int lim=(1LL<<(h-1));
    for(int msk=0;msk<lim;msk++)
    {
        ses=min(solve(msk),ses);
    }
    cout<<ses<<endl;



















    return 0;

}













Measured memory_bytes: 256
fn main() {
    let scan = std::io::stdin();
    let mut line = String::new();
    let _ = scan.read_line(&mut line);
    let vec: Vec<&str> = line.split_whitespace().collect();
    let n: i32 = vec[0].parse().unwrap();

    let mut line = String::new();
    let _ = scan.read_line(&mut line);
    let vec: Vec<&str> = line.split_whitespace().collect();

    let mut ans: i32 = 0;
    let mut data: Vec<i32> = Vec::new();

    for x in 0..n{
        data.push(vec[x as usize].parse().unwrap());
    }

    'l1:loop{
        for x in 0..data.len(){
            if data[x] % 2 == 1{
                break 'l1;
            }else{
                data[x] = data[x] / 2;
            }
        }
        ans = ans + 1;
    }

    println!("{}",ans);
}


Measured memory_bytes: 4352
S = int(input())
MOD = 10 ** 9 + 7

#dp[i]最後に切った場所がi　スタートが1なのは、そこまでの切り方が1通りなので
#３以下はダメなので、3個前の結果を見るようにする
dp =  [0] * (S+1)
dp[0] = 1

for i in range(1, S+1):
    #たとえばi=6のとき、i=6で初めて切れ目を入れる時で＋１、i=3に切れ目をいれるときで＋１で合計＋２
    for j in range(0, (i-3)+1):
        dp[i] += dp[j]
        dp[i] %= MOD
print(dp[S])        

Measured memory_bytes: 64852
#include<bits/stdc++.h>
#define vi vector<int>
#define vb vector<bool>

using namespace std;

int main(){
    int n,k;
    cin>>n>>k;
    vi arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    vb dp(k+1,false);
    for(int i=1;i<=k;i++){
        for(int j=0;j<n;j++){
            if(i-arr[j]>=0){
                if(!dp[i-arr[j]]){
                    dp[i]=true;
                    break;
                }
            }
        }
    }
    if(dp[k]) cout<<"First";
    else cout<<"Second";
}

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

#define debug(x) cerr << #x << ": " << x << endl
#define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << endl
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
const ll INF = LLONG_MAX/2;
const ll MOD = 1e9+7;
const double EPS=1e-12;

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N,D;cin>>N>>D;
  ll X[N][D];
  for(ll i=0;i<N;i++){
    for(ll j=0;j<D;j++){
      cin>>X[i][j];
    }
  }
  ll ans=0;
  for(ll i=0;i<N;i++){
    for(ll j=i+1;j<N;j++){
      ll dis=0;
      for(ll k=0;k<D;k++){
        dis+=(X[i][k]-X[j][k])*(X[i][k]-X[j][k]);
      }
      ll rd=sqrt(dis)+0.5;
      if(rd*rd==dis)ans++;
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main()
{
	int N,Y;

	cin >> N >> Y;

	for(int i=0;i<N+1;i++)
	{
		for(int j=0;j<N+1;j++)
		{
			int k = N - (i+j);
			if(k < 0)continue;
			
			if( 10000*i+5000*j+1000*k == Y)
			{
				cout << i << " " << j << " " << k << endl;
				return 0;
			}
		}
	}

	cout << -1 << " " << -1 << " " << -1 << endl;

	return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

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

	ll N; cin >> N;
	map<ll,ll> mp;

	for (int i = 0;i < N;i++){
		ll A; cin >> A;
		mp[A]++;
	}
	
	ll l1 = 0;
	ll l2 = 0;

	for(auto&& i:mp){
		if(i.second >= 4){
			l1 = l2 = i.first;
		}
		else if(i.second >= 2){
			l2 = l1;
			l1 = i.first;
		}
	}

	cout << l1*l2 << endl;

	return 0;

}


Measured memory_bytes: 6528
#coding: utf-8

s=gets.chomp
ans=Array.new(0)
i=0
while(i<s.length)
	unless(s[i]=='B')
		ans << s[i]
	else
		ans.delete_at(-1)
	end
	i+=1
end
i=0
while(i<ans.length)
	print(ans[i])
	i+=1
end
	print("\n")


Measured memory_bytes: 1788
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int n;
    ll a[200005] = {}, z = 0, y = 0;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i], z += a[i], y += a[i] * a[i] % mod;
    z %= mod; y %= mod;
    cout << (z * z - y) % mod * 500000004 % mod;
}


Measured memory_bytes: 5200
#include <stdio.h>
#include <string>
#include <iostream>
#include <iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <math.h>
#define MOD 1000000007
using namespace std;

int main(void){
    int n;
    long long ans=1;
    cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    sort(a.begin(),a.end());
    if(n%2==0 && a[0]!=1){
        cout << 0 << endl;
        return 0;
    }
    if(n&2==1 && a[0]!=0){
        cout << 0 << endl;
        return 0;
    }
    for(int i=0; i+1<n; i++){
        if((i%2) ^ (n%2)){
            if(a[i+1]-a[i]!=2){
                cout << 0 << endl;
                return 0;
            }
        }else {
            if(a[i+1]!=a[i]){
                cout << 0 << endl;
                return 0;
            }else ans=(ans*2)%MOD;
        }
    }
  	cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640
s = input()
buf = 0
str_len = len(s)
total = 0

while buf < str_len:
    l_count = 0
    r_count = 0

    while buf < str_len and s[buf] == "<":
        l_count += 1
        buf += 1

    while buf < str_len and s[buf] == ">":
        r_count += 1
        buf += 1

    f = lambda x : x * ( x + 1 ) // 2
    n = max(l_count, r_count)
    total += f(n)
    m = min(l_count, r_count) - 1
    total += f(m)

print(total)

Measured memory_bytes: 4116
const MOD: u64 = 1000000007;

fn main() {
	let mut s = String::new();
	use std::io::Read;
	std::io::stdin().read_to_string(&mut s).unwrap();
	let mut s = s.split_whitespace();
	let n: u64 = s.next().unwrap().parse().unwrap();
	let mut cnt = [0; 60];
	for a in s.map(|a| a.parse::<u64>().unwrap()) {
		for i in 0..60 {
			if a & (1 << i) != 0 {
				cnt[i] += 1;
			}
		}
	}
	println!("{}", (0..60).fold(0, |r, i| (r + ((1 << i) % MOD) * (cnt[i] * (n - cnt[i]) % MOD)) % MOD));
}


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

int main() {
  int64_t N;
  int64_t ans;
  int64_t preans;
  int64_t newans;
  
  cin >> N;
  
  for(int i = 0; i < N; i++){
    if(i == 0){
      preans = 2;
      ans = 1;
    }
    else{
      newans = ans + preans;
      preans = ans;
      ans = newans;
    }
  }
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,k;
int d,a;
set<int> s;
int main()
{
    cin>>n>>k;
    for(int i=0;i<k;i++){
        cin>>d;
        for(int j=0;j<d;j++){
            cin>>a;
            s.insert(a);
        }
    }
    int c=s.size();
    cout<<n-c;
    return 0;
}

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

int main() {

	vector<vector<int>> c(3, vector<int>(3));

	for (int i= 0;i < 3;i++) {
		for (int j = 0;j < 3;j++) {
			cin >> c.at(i).at(j);
		}
	}

	bool t = true;
	for (int i = 0;i < 2;i++) {
		if (c.at(i).at(1) - c.at(i).at(0) == c.at(i + 1).at(1) - c.at(i + 1).at(0) && c.at(i).at(2) - c.at(i).at(0) == c.at(i + 1).at(2) - c.at(i + 1).at(0))
			t = true;

		else {
			t = false;
			break;
		}
	}

		if (t)
			cout << "Yes";
		else
			cout << "No";
}



Measured memory_bytes: 256
from itertools import accumulate, chain

N,M,K = map(int,input().split())
A = tuple(chain((0,),accumulate(map(int,input().split()))))
B = tuple(chain((0,),accumulate(map(int,input().split()))))

def it():
    j = M
    for i,at in enumerate(A):
        while j >= 0 and at+B[j] > K:
            j -= 1
        if j >= 0:
            yield i+j

print(max(it()))

Measured memory_bytes: 48308
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<time.h>
#include<iomanip>
#define PI 3.14159265358979

using namespace std;
typedef unsigned long long ull;

int main() {
	double a, b, x_;
	cin >> a >> b >> x_;
	double x = x_ / a;
	if (x * 2 / b <= a) {
		cout << setprecision(200) << atan2(b, x * 2 / b) * 180 / PI;
	}
	else {
		double y = x * 2 / a - b;
		cout << setprecision(200) << atan2(b - y, a) / PI * 180;
	}
}

/*
*/

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
int main(){
	int h,w;
	cin>>h>>w;
	vector<int>s(h*w),map(h*w,99999999);
	rep(i,h){
		rep(j,w){
			char tmp;
			cin>>tmp;
			if(tmp=='.'){
				s[i*w+j]=1;
			}else{
				s[i*w+j]=0;
			}
		}
	}
	vector<int>list;
	int max = 0;
	rep(i,h*w){
		if(s[i]==0)continue;
		rep(j,h*w)map[j]=999999999;
		list.push_back(i);
		map[i] = 0;
		while(list.size()>0){
		/*
		cout<<"list is {";
		rep(i,list.size()){
			cout<<list[i];
		}
		cout<<endl;
		*/


		if(list[0]%w>0){//not left
			if(map[list[0]-1]>map[list[0]]+1&&s[list[0]-1]==1){
				map[list[0]-1]=map[list[0]]+1;
				list.push_back(list[0]-1);
			}
		}
		if(list[0]%w<w-1){//not right
			if(map[list[0]+1]>map[list[0]]+1&&s[list[0]+1]==1){
				map[list[0]+1]=map[list[0]]+1;
				list.push_back(list[0]+1);
				}
		}
		if(list[0]>=w){//not up
			if(map[list[0]-w]>map[list[0]]+1&&s[list[0]-w]==1){
				map[list[0]-w]=map[list[0]]+1;
				list.push_back(list[0]-w);
			}
		}
		if(list[0]<(h-1)*w){//not down
			if(map[list[0]+w]>map[list[0]]+1&&s[list[0]+w]==1){
				map[list[0]+w]=map[list[0]]+1;
				list.push_back(list[0]+w);
			}
		}
		list.erase(list.begin());
	}
	rep(i,h*w){
		if(max<map[i]&&s[i]==1)max=map[i];
	}
	}
	cout<<max<<endl;



	return 0;
}

Measured memory_bytes: 256
use proconio::input;

fn main() {
    input! {
        n: usize,
        a: [i64; n],
    }

    let mut ans = 0i64;
    for i in 0..n {
        let ai = a[i];
        let i = i + 1;

        if ai % 2 == 1 && i % 2 == 1 {
            ans += 1;
        }
    }
    println!("{}", ans);
}


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

int pow(int a,int b){
  int tmp=1;
  for(int ii=0;ii<b;ii++){
    tmp*=a;
  }
  return tmp;
}

main(){
  int N;
  cin >> N;
  int n=0;//桁数
  int tmp=N;
  for(int ii=0;ii<N;ii++){//Nlog10
    tmp/=10;
    n++;
    if(tmp==0)break;
    //    cout << tmp << endl;
  }
  //  cout << n << endl;
  //  cout << nn << endl;
  int ans=0;
  for(int kk=3;kk<=n;kk++){//桁数
    int nn=1;
    for(int ii=0;ii<kk;ii++){//3^kk
      nn*=3;
    }
    for(int jj=0;jj<nn;jj++){//値決める。
      int tmp=jj;
      int cnt7=1;
      int cnt5=1;
      int cnt3=1;
      int tmp2=0;
      for(int ii=0;ii<kk;ii++){//値確認
	//      cout << tmp%3;
	if(tmp%3==0){
	  if(ii==0)tmp2+=7;
	  else tmp2+=7*pow(10,ii);
	  cnt7=0;
	}
	else if(tmp%3==1){
	  if(ii==0)tmp2+=5;
	  else tmp2+=5*pow(10,ii);
	  cnt5=0;
	}
	else{
	  if(ii==0)tmp2+=3;
	  else tmp2+=3*pow(10,ii);
	  cnt3=0;
	}
	tmp/=3;
      }
      //      cout << tmp2 << endl;
      //    printf("\n%d %d %d",cnt7,cnt5,cnt3);
      if(cnt7==0&&cnt5==0&&cnt3==0&&tmp2<=N)ans++;
      //      cout << "a" << endl;
      //    cout << endl;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll/*, vl, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
typedef pair<ll, ll> pl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, n) for(ll i = 1; i <= ll(n); i++)
//#define rep(i, k, n) for(ll i = k-1; i < ll(n); i++)
//#define rep2(i, k, n) for(ll i = k; i <= ll(n); i++)
#define all(v) (v).begin(), (v).end()
ll mod(ll a, ll b) {if(b == 0) return 0; return (a % b + b) % b;}
bool chmin(ll &a, ll b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 1e9;
const char newl = '\n';

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

  ll n, k;
  cin >> n >> k;
  vl a(n);
  rep(i, n) cin >> a[i];
  
  rep(i, n-k) cout << (a[i]<a[k+i] ? "Yes" : "No") << newl;
  return 0;
}

Measured memory_bytes: 4776