akhauriyash/Code-Regression huggingface dataset:
import java.io.PrintWriter

fun main(args: Array<String>) {
    PrintWriter(System.out).use { out ->
        solve(out)
        out.flush()
    }
}

fun solve(out: PrintWriter) {
    val (n, k, s) = readStringList()
    val a = mutableListOf<String>()
    repeat(k.toInt()) {
        a += s
    }
    repeat (n.toInt() - k.toInt()) {
        a += if (s.toInt() == 1000000000) "1" else "1000000000"
    }
    println(a.joinToString(" "))
}

fun readInteger() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntegerList() = readStringList().map(String::toInt)
fun readLongList() = readStringList().map(String::toLong)
fun readDoubleList() = readStringList().map(String::toDouble)


Measured memory_bytes: 40912
import java.util.Scanner;

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

		int n = sc.nextInt();
		n = n % 100;
		n = n % 10;

		switch (n) {
		case 2:
		case 4:
		case 5:
		case 7:
		case 9:
			System.out.println("hon");
			break;
		case 0:
		case 1:
		case 6:
		case 8:
			System.out.println("pon");
			break;
		case 3:
			System.out.println("bon");
			break;
		}
	}
}

Measured memory_bytes: 35580
N=int(input())
B=list(map(int,input().split()))

if N==2:print(B[0]*2)
else:
  A = [B[0]]
  for i in range(N-2):
    A.append(min(B[i],B[i+1]))
  A.append(B[-1])
  print(sum(A))

Measured memory_bytes: 8996
N,K = map(int,input().split())
A = list(map(int,input().split()))
b,c,d = 0,0,0
mod = 10**9+7
B = []
C = []
D = []
for a in A:
    if a < 0:
        b += 1
        B.append(a)
    elif a == 0:
        c += 1
        C.append(a)
    else:
        d += 1
        D.append(a)
if B:
    B.sort()
if D:
    D.sort(reverse = True)
if K > b+d:
    print(0)
elif K == b+d and K< N and b%2 == 1:
    print(0)
elif K == N:
    ans = 1
    for i in range(N):
        ans = ans * A[i] % mod
    print(ans)
elif b == N and K % 2 == 1:
    ans = 1
    for i in range(1,K+1):
        ans = ans*B[-i]%mod
    print(ans)
elif K<b and d == 0 and K%2 == 1:
    print(0)
else:
    bi = 0
    di = 0
    ans = 1
    while(K>1):
        if (bi >= b-1) or (di+1< d and D[di]*D[di+1] > B[bi]*B[bi+1]):
            ans = ans*D[di]%mod
            ans = ans*D[di+1]%mod
            di += 2
        else:
            ans = ans*B[bi]%mod
            ans = ans*B[bi+1]%mod
            bi += 2
        K -= 2
    if K == 1:
        ans = ans * D[di] % mod
    print(ans)

Measured memory_bytes: 104728
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
long DP[100001*101];
void Calc(){
	int N = rei();
	long W = rel();
	for(int j=1;j<=100000;j++){
		DP[j] = W+1;
	}
	for(int i=0;i<N;i++){
		for(int j=0;j<=100000;j++){
			DP[(i+1)*100001+j] = DP[i*100001+j];
		}
		long w = rel();
		int v = rei();
		for(int j=v;j<=100000;j++){
			DP[(i+1)*100001+j] = min(DP[(i+1)*100001+j],DP[i*100001+j-v]+w);
		}
	}
	long ans = 0;
	for(int i=1;i<=100000;i++){
		if(DP[N*100001+i] <= W){
			ans = i;
		}
	}
	cout << ans << endl;
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}

Measured memory_bytes: 79232
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String text = "";
        while (!(text = br.readLine()).equals("-")) {
            int n = Integer.parseInt(br.readLine());
            while (n-- > 0) {
                int i = Integer.parseInt(br.readLine());
                text = text.substring(i) + text.substring(0, i);
            }
            bw.append(text + "\n");
        }

        bw.flush();
    }

}


Measured memory_bytes: 24324
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <ctime>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <iterator>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) container.begin(), container.end()
#define RALL(container) container.rbegin(), container.rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class S, class T> pair<S,T> operator+(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first+t.first, s.second+t.second);}
template<class S, class T> pair<S,T> operator-(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first-t.first, s.second-t.second);}

const int INF = 1<<28;
const double EPS = 1e-10;
const int MOD = 1000000007;

#define X real()
#define Y imag()

typedef complex<double> P;
struct L{
	P p1, p2;
	L(P p1, P p2):p1(p1), p2(p2){}
	L(){}
};
istream& operator>>(istream &is, P &p) {
	double x, y;
	is >> x >> y;
	p = P(x, y);
	return is;
}
inline int sig(double x) { return (abs(x) < EPS ? 0 : x > 0 ? 1 : -1); }
inline double norm(const P &p){return p.X*p.X+p.Y*p.Y;}
inline double inp(const P& a, const P& b){return (conj(a)*b).X;}
inline double outp(const P& a, const P& b){return (conj(a)*b).Y;}


int T;

int main(){
	ios::sync_with_stdio(false);
	cin >> T;
	while(T--){
		P p1, p2, p3, p4;
		cin >> p1 >> p2 >> p3 >> p4;
		puts(!sig(inp(p2-p1, (p4-p3)*P(0., 1.))) ? "YES" : "NO");
	}
	return 0;
}

Measured memory_bytes: 1224
#include <iostream>
#include <float.h>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <fstream>
#include <queue>
#include <math.h>
#include <set>
#include <stdlib.h>
#include <time.h>
#include <list>
#include <stack>
#include <queue>

#define For(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  For(i,0,n)

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
#define SORT(c) sort((c).begin(),(c).end())
#define vi(m,a) vector<int> m(a)
#define vti(m,a,i) vector<vector<int>> m(a,vector<int>(i))
#define ALL(it,a) for(auto it = a.begin(); it!=a.end(); it++)
#define Fe(it,a) for(auto &it : a)
#define all(a) begin(a),end(a)

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
#define WARU 1000000007;

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

string result;
string str;
int n;
bool solve(vector<char> d,string init) {
	For(i, 1, n) {
		if (d[i] == 'S') {
			if (str[i] == 'o') {
				if (d[i - 1] == 'S')
					d[(i + 1) % n] = 'S';
				else
					d[(i + 1) % n] = 'W';
			}
			else {
				if (d[i - 1] == 'S')
					d[(i + 1) % n] = 'W';
				else
					d[(i + 1) % n] = 'S';
			}

		}
		else {
			if (str[i] == 'o') {
				if (d[i - 1] == 'S')
					d[(i + 1) % n] = 'W';
				else
					d[(i + 1) % n] = 'S';
			}
			else {
				if (d[i - 1] == 'W')
					d[(i + 1) % n] = 'W';
				else
					d[(i + 1) % n] = 'S';
			}
		}
	}
	if (str[0] == 'o') {
		if (d[0] == 'S' && d[n - 1] != d[1]) {
			return false;
		}
		if (d[0] == 'W' && d[n - 1] == d[1]) {
			return false;
		}
	}
	else {
		if (d[0] == 'S' && d[n - 1] == d[1]) {
			return false;
		}
		if (d[0] == 'W' && d[n - 1] != d[1]) {
			return false;
		}
	}
	string str(d.begin(),d.end());
	if (d[n - 1] == init[0] && d[0] == init[1] && d[1] == init[2]) {
		string str(d.begin(),d.end());
		result = str;
		return true;
	}
	return false;
}


int main() {
	cin >> n;
	cin >> str;
	vector<char> d(n);
	auto flag = false;
	auto tmp = d;
	string uso[] = { "SSW","WSS","SWS","WWW" };
	string honto[] = { "SSS","WSW","SWW","WWS" };
	if (str[0] != 'o') {
		rep(i, 4) {
			tmp[0] = uso[i][1];
			tmp[1] = uso[i][2];
			tmp[n - 1] = uso[i][0];
			flag = solve(tmp,uso[i]);
			if (flag)
				break;
		}
	}
	else {
		rep(i, 4) {
			tmp[0] = honto[i][1];
			tmp[1] = honto[i][2];
			tmp[n - 1] = honto[i][0];
			flag = solve(tmp,honto[i]);
			if (flag)
				break;
		}
	}
	if (flag)
		cout << result << endl;
	else
		cout << -1 << endl;
}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n); i >= 0; i--)
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int INF = 2100100100;
const int MOD = 1e9 + 7;

// 多次元 vector 生成
template <class T> vector<T> make_vec(size_t a) { return vector<T>(a); }
template <class T, class... Ts> auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T> bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<int> p(n), tmp(n);
    REP(i, n) {
        cin >> p.at(i);
        tmp[i] = p[i];
    }
    sort(ALL(p));
    int dif = 0;
    REP(i, n) {
        if (p[i] != tmp[i]) {
            dif++;
        }
    }
    if (dif <= 2) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
 
   //  String[] nyu=sc.nextLine().split("");

     String nyu=sc.nextLine();
//int A=Integer.parseInt(nyu[0]);
//int B=Integer.parseInt(nyu[1]);
int C=Integer.parseInt(nyu);
     nyu=sc.nextLine();

int D=Integer.parseInt(nyu);
     nyu=sc.nextLine();

int E=Integer.parseInt(nyu);


//double A=Double.parseDouble(nyu[0]);
//double B=Double.parseDouble(nyu[1]);
/*
switch(C){
case 7:
case 5:
case 3:
System.out.println("YES") ;
break;
default:
System.out.println("NO") ;

break;
}
*/

int res=(C-D)%E;
//if(res<=D){

System.out.println(res);
//}else{
//System.out.println("No");

//}




	}
}

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

int main(void)
{
    char stn[3];
    char t[2];
    char u[2];
    char v[2];

    scanf("%s", stn);

    strncpy(t, stn, 1);
    t[1] = '\0';
    strncpy(u, stn+1, 1);
    u[1] = '\0';
    strncpy(v, stn+2, 1);
    v[1] = '\0';

    if ((t[0]==u[0])&&(t[0]==v[0])){
        printf("No");
    }else{
        printf("Yes");
    }

    return 0;
}

Measured memory_bytes: 128
from numpy import*
from scipy.sparse import*
def main():
  f=csgraph.floyd_warshall
  t=int32(open(0).read().split())
  n,m,l=t[:3]
  t=t[3:]
  m*=3
  print('\n'.join(map(str,map(int,clip(f(f(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),(n+1,n+1)),0)<=l)[t[m+1::2],t[m+2::2]],0,n)%n-1))))
main()

Measured memory_bytes: 41976
import numpy as np
N,M,X= map(int, input().split())
q = [list(map(int, input().split())) for _ in range(N)]
q = np.array(q)
ans = []
for j in range(2**N):
    list = []
    cost = 0
    for k in range(N):
        if (j >> k)&1:
            list.append(1)
        else:
            list.append(0)
    list = np.array(list)
    for l in range(N):
        cost +=  q[l] * list[l]
    if min(cost[1:]) >= X:
        ans.append(cost[0])
if len(ans) == 0:
    ans.append(-1)
print(min(ans))

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String temp[];
		int num1;
		int num2;
		int sum;

		temp = br.readLine().split(" ");
		num1 = Integer.parseInt(temp[0]);
		num2 = Integer.parseInt(temp[1]);
		sum = num1 + num2;

		if (sum >= 10 ) {
			System.out.println("error");
		} else {
			System.out.println(sum);
		}
	}
}


Measured memory_bytes: 21204
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
int main(){
    string s[10];
    int h,w,K,ANS=1e9;
    cin>>h>>w>>K;
    rep(i,h) cin>>s[i];
    rep(i,pow(2,h-1)){
        int z=1,ans=0;
        vec A;
        int p=i;
        A.push_back(0);
        rep(j,h-1){
            if(p%2) A.push_back(j+1),ans++;
            p=p/2;
        }
        A.push_back(h);
        int B[10]={0};
        rep(j,w){
            int C[10]={0};
            rep(k,A.size()-1){
                for(int l=A[k];l<A[k+1];l++) if(s[l][j]=='1') C[k]++;
            }
            rep(k,A.size()-1) if(C[k]>K) z=0;
            int Z=0;
            rep(k,A.size()-1){
                if(B[k]+C[k]>K) Z=1;
            }
            if(Z){
                rep(k,A.size()-1) B[k]=C[k];
                ans++;
            }
            else rep(k,A.size()-1) B[k]+=C[k];
        }
        if(z) ANS=min(ANS,ans);
    }
    cout<<ANS<<"\n";
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int partition(vector<int>& v, int left, int right) {
    int base = v[right];
    int idx = left - 1;
    for (int i = left; i < right; ++i) {
        if (v[i] <= base) {
            ++idx;
            swap(v[idx], v[i]);
        }
    }
    ++idx;
    swap(v[idx], v[right]);
    return idx;
}

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

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

    int idx = partition(a, 0, n - 1);

    if (idx == 0)
        cout << '[' << a[0] << ']';
    else
        cout << a[0];
    for (int i = 1; i < n; ++i) {
        cout << ' ';
        if (i == idx)
            cout << '[';
        cout << a[i];
        if (i == idx)
            cout << ']';
    }
    cout << '\n';
}



Measured memory_bytes: 3080
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<vector>
#include<queue>
#include<stack>
#include<map>
using namespace std;
#define FOR(i,s,e) for (int i=s;i<e;i++)
#define FOE(i,s,e) for (int i=s;i<=e;i++)
#define FOD(i,s,e) for (int i=s;i>=e;i--)
#define SET(a,e) memset(a,e,sizeof(a))
#define LL long long
#define LD long double
#define pb push_back
#define x first
#define y second
#define PII pair<int,int>
#define PLI pair<LL,int>
#define PIL pair<int,LL>
#define PLL pair<LL,LL>
#define eps 1e-9
#define mp make_pair

char s[105];
int n;

int main () {
	scanf("%s",s);
	n=strlen(s);
	printf("%c%d%c",s[0],n-2,s[n-1]);
	return 0;	
}

Measured memory_bytes: 128
class EightQueen
  SUCCESS = 0
  FAIL = 1
  FREE = 0
  NOT_FREE = 1
  N=8

  def initialize
    @row = []
    @col = Array.new(N, FREE)
    @down = Array.new(2*N-1, FREE) # x - y + (N - 1)
    @up = Array.new(2*N-1, FREE)   # x + y
    @x = Array.new(8).map { Array.new(8, false) }

    gets.to_i.times do
      i, j = gets.split.map &:to_i
      @x[i][j] = true
    end
  end

  def print_queen
    (0...N).each do |i|
      (0...N).each do |j|
        if @x[i][j] && @row[i] != j
          return FAIL
        end
      end
    end

    (0...N).each do |i|
      (0...N).each do |j|
        print @row[i] == j ? 'Q' : '.'
      end
      puts
    end
    return SUCCESS
  end

  def solve(i)
    (0..7).each do |j|
      if @col[j] == FREE && @down[i-j+(N-1)] == FREE && @up[i+j] == FREE
        @row[i] = j
        @col[j] = @down[i-j+(N-1)] = @up[i+j] = NOT_FREE

        if (i == 7)
          return if print_queen == SUCCESS
        else
          solve(i + 1)
        end
        @row[i] = nil
        @col[j] = @down[i-j+(N-1)] = @up[i+j] = FREE
      end
    end
  end
end

eq = EightQueen.new
eq.solve(0)

Measured memory_bytes: 8756
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define INF 2e9
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n,w,h,count=0;
  cin>>n>>h>>w;
  count+=n-h+1;
  cout<<count*(n-w+1)<<'\n';
  return(0);
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		long sum0 = 0;
		long sum1 = 0;
		for(int i=1; i<=N; ++i) {
			if(i % K == 0) {
				sum0++;
			}
			else if(i%K == (K/2) && K%2==0) {
				sum1++;
			}
		}
		long ans = sum0*sum0*sum0;
		ans += sum1*sum1*sum1;
		System.out.println(ans);
	}
}


Measured memory_bytes: 23508
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int A,B,C,X,Y;
	A=sc.nextInt();
	B=sc.nextInt();
	C=sc.nextInt();
	X=sc.nextInt();
	Y=sc.nextInt();
	C*=2;
	if(C>=A+B) {
		System.out.println(A*X+B*Y);
	}else {
		int min=X>Y?Y:X;
		int result=0;
		result+=(min*C);
		if(X==Y) {
			System.out.println(result);
		}else if(X>Y) {
			int cha=X-Y;
			if(C<A) {
				result+=(C*cha);
				System.out.println(result);
			}else {
				result+=(A*cha);
				System.out.println(result);
			}
		}else if(X<Y) {
			int cha=Y-X;
			if(C<B) {
				result+=(C*cha);
				System.out.println(result);
			}else {
				result+=(B*cha);
				System.out.println(result);
			}
		}
	}
	
	
}
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef long int li;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef pair<double, double>P;
typedef tuple<ll, int, int>T;
#define PI 3.14159265358979


int main(){
  int N,K;
  cin>>N>>K;
  vector<int>A(N);
  vector<int>dp(K+1);
  rep(i,N){cin>>A[i];}
  rep(i,K+1){dp[i]=0;}
  for(int i=1;i<=K;i++){
    rep(j,N){
      if(i-A[j]>=0){
        if(dp[i-A[j]]==0){
          dp[i]=1;
        }
      }
    }
  }
  if(dp[K]==1){cout<<"First";}
  else{cout<<"Second";}
}

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

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

const long long INF = 1LL << 60;

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

    int B[M];
    int ans = 0;

    rep(i, M) {
        cin >> B[i];
    }
    rep(i, N) {
        int plus = 0;
        rep(j, M) {
            int a;
            cin >> a;
            plus += (a * B[j]);
        }
        if (plus + C > 0) ans++;
    }

    cout << ans << endl;

    return 0;
}

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

#ifdef LOCAL
#include "debug.h"
#else
#define DEBUG(...)
#endif

constexpr int n = 365, m = 26;
int c[m], s[n][m];

int type[n];
int score(int lim = n) {
  static int last[m];
  fill(begin(last), end(last), -1);
  int res = 0;
  for (int i = 0; i < lim; ++i) {
    res += s[i][type[i]];
    last[type[i]] = i;
    for (int j = 0; j < m; ++j) {
      res -= c[j] * (i - last[j]);
    }
  }
  return res;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  // cin.ignore();
  int _n;
  cin >> _n;
  assert(_n == n);
  for (int j = 0; j < m; ++j) {
    cin >> c[j];
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      cin >> s[i][j];
    }
  }
  for (int i = 0; i < n; ++i) {
    // cout << type[i] + 1 << '\n';
    cin >> type[i];
    --type[i];
  }
  for (int i = 0; i < n; ++i) {
    cout << score(i + 1) << '\n';
  }
}


Measured memory_bytes: 3652
package main
 
import (
	"fmt"
)
 
func main() {
	var n,l int
	var sum int
	fmt.Scanf("%d %d", &n,&l)
	
	k := 1-l
	
	// 単純sum
	sum = l*n - n + n*(n+1)/2
	
	if (k >= l && k <= n) {
	} else {
	    if l > 0 {
	        sum -= l
	    } else {
	        sum -= (l+n-1)
	    }
	}

    fmt.Printf("%d",sum)
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define REP(i,n) for(int64_t i=0;i<(n);i++)
#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REV(c) reverse((c).begin(),(c).end())
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define Yes cout << "Yes" << endl;
#define No cout << "No" << endl;
#define COUTDOUBLE(d,i) cout << setprecision((i)) << (d) << endl;
#define VIN(n,v) for(int64_t i=0;i<(n);i++){cin >> (v).at(i);}

using namespace std;
typedef int64_t I;
typedef pair<I,I> P;
typedef vector<I> V;

I MOD = pow(10,9)+7;

// 最大公約数
I gcd(I a, I b) {
  return b != 0 ? gcd(b, a % b) : a;
}

// 最小公倍数
I lcm(I a, I b) {
  return a * b / gcd(a, b);
}

int ctoi(char c){
  return c - '0';
}

int main(){
  I n,a,b,c,d,e;
  cin >> n >> a >> b >> c >> d >> e;
  I mi = LONG_MAX;
  mi = min(a,mi);
  mi = min(b,mi);
  mi = min(c,mi);
  mi = min(d,mi);
  mi = min(e,mi);
  I t;
  if (n > mi){
    t = n / mi;
    if (n % mi != 0){
      t++;
    }
  }else{
    t = 1;
  }
  cout << t + 4 << endl;
  return 0;
}



Measured memory_bytes: 256
<?php
# 入力部
// fscanf(STDIN, "%d", $a);
// fscanf(STDIN, "%d %d", $a, $b);
// $s = fgets(STDIN);
fscanf(STDIN, "%d", $n);

# 処理部
// $arr = explode(" ", $s);
// for ($i = 0; $n > $x * $i; $i++) {
// }
// if (strpos($s, 'RRR') !== false) {
//   $r = 3;
// } elseif (strpos($s, 'RR') !== false) {
//   $r = 2;
// } elseif (strpos($s, 'R') !== false) {
//   $r = 1;
// } else {
//   $r = 0;
// }
// $s = "No";
// if ($x >= 30) {
//   $s = "Yes";
// }
// for ($i = 0; $i * 1000 < $n; $i++) {
// }
// $c = "a";
// if (ctype_upper($a)) {
//   $c = "A";
// }
// for ($i = 0; $i < count($arr); $i++) {
//   if ($i + 1 != $arr[$i]) {
//     $r = $i + 1;
//   }
// }
$unit;
switch ($n % 10) {
  case 0:
  case 1:
  case 6:
  case 8:
    $unit = "pon";
    break;
  case 3:
    $unit = "bon";
    break;
  default:
    $unit = "hon";
    break;
}

# 出力部
echo $unit . "\n";
// echo ($i * 1000) - $n . "\n";

Measured memory_bytes: 16228
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <stack>
#include <memory.h>
#include <list>
#include <numeric>
#include <functional>
#include <complex>
#include <cassert>
#include <regex>
#include <random>

#define ll long long
#define ld long double
#define ull unsigned ll
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pii pair<int,int> 
#define vi vector<int>
#define vpii vector<pii>
#define vvi vector<vector<int>>
#define forn(it,from,to) for(int (it)=from; (it)<to; (it)++)
const int  Inf = 2 * 1000 * 1000 * 1000;
ll LINF = (ll)4e18;
using namespace std;
#define M_PI       3.14159265358979323846   // pi

const int nax = 1005;

const int mod = 1e9 + 7;

int D[nax][nax];

void inc(int &a, int b) {
	a += b;
	if (a >= mod) a -= mod;
}

string a[nax];

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
	//freopen("sum.in", "r", stdin);
	//freopen("sum.out", "w", stdout);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int h, w;
	cin >> h >> w;
	for (int i = 0; i < h; i++) {
		cin >> a[i];
	}

	D[0][0] = 1;

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (a[i][j] != '.') continue;
			inc(D[i + 1][j], D[i][j]);
			inc(D[i][j + 1], D[i][j]);
		}
	}
	cout << D[h - 1][w - 1];
 	return 0;
}

Measured memory_bytes: 5248
using System;

namespace ABC136
{
    class A
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int A = int.Parse(input[0]);
            int B = int.Parse(input[1]);
            int C = int.Parse(input[2]);

            if (C - (A - B) <= 0)
            {
                Console.WriteLine(0);
                return;
            }
            else
            {
                Console.WriteLine(C - (A - B));
            }
        }
    }
}

Measured memory_bytes: 13140
use std::collections::VecDeque;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        h: usize,
        w: usize,
        board: [chars; h]
    }
 
    let mut tbl = vec![vec![None; w]; h];
    let mut queue = VecDeque::new();
    for j in 0..h {
        for i in 0..w {
            // kuro
            if board[j][i] == '#' {
                queue.push_back((j, i, 0));
            }
        }
    }
 
    while let Some((j, i, v)) = queue.pop_front() {
        if tbl[j][i].is_some() {
            continue;
        }
        tbl[j][i] = Some(v);
        for &(jj, ii) in [(-1, 0), (1, 0), (0, -1), (0, 1)].iter() {
            let j = j as i64 + jj;
            let i = i as i64 + ii;
            if j < 0 || i < 0 {
                continue;
            }
            let j = j as usize;
            let i = i as usize;
            if j >= h || i >= w {
                continue;
            }
            queue.push_back((j, i, v + 1));
        }
    }

    let result = tbl.iter().filter_map(|line| line.iter().filter_map(|v| *v).max()).max().unwrap();
    println!("{}", result);
}


Measured memory_bytes: 114676
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
using namespace std;
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define INF 1145141919810364364
#define int long long
#define all(vec) vec.begin(),vec.end()
#define P pair<int,int>
#define S second
#define F first

int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
bool prime(int x) {
	for (int i = 2; i <= sqrt(x); i++) {
		if (x%i == 0)return false;
	}
	return true;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}

int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}

int n, m, l, q;
int d[310][310], d2[310][310];

signed main() {
	cin >> n >> m >> l;
	for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) {
		d[i][j] = INF;
		d2[i][j] = INF;
	}
	for (int i = 0; i < m; i++) {
		int a, b, c; cin >> a >> b >> c;
		d[a][b] = c;
		d[b][a] = c;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
			}
		}
	}
	for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)if (d[i][j] <= l)d2[i][j] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				d2[j][k] = min(d2[j][k], d2[j][i] + d2[i][k]);
			}
		}
	}
	cin >> q;
	for (int i = 0; i < q; i++) {
		int a, b; cin >> a >> b;
		if (d2[a][b] == INF)cout << -1 << endl;
		else cout << d2[a][b] - 1 << endl;
	}
}

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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define INF         INT_MAX/3
#define LLINF       LLONG_MAX/3
#define MOD         (1000000007LL)
#define MODA(a, b)  a=((a)+(b))%MOD
#define MODP(a, b)  a=((a)*(b))%MOD
#define inc(i, l, r)   for(int i=(l);i<(r);i++)
#define dec(i, l, r)   for(int i=(r)-1;i>=(l);i--)
#define pb          push_back
#define se          second
#define fi          first
#define mset(a, b)  memset(a, b, sizeof(a))

using LL  = long long;
using G   = vector<vector<int>>;

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

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    int n;cin >> n;
    inc(i, n, 1000){
        if(i%10 == i/10%10 && i%10 == i/100%10){
            cout << i << endl;
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define ALL(n) begin(n),end(n)
#define IN(a, x, b) (a<=x && x<b)
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
template<class T> inline T CHMAX(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T CHMIN(T & a, const T b) { return a = (a > b) ? b : a; }

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);

int main()
{
    INIT;
    int N, X;
    cin >> N >> X;
    vector<int> L(N);
    REP(i,N) cin >> L.at(i); 
    vector<int> D(N+1);
    int ans = 0;
    D.at(0) = 0;
    if(D.at(0) <= X) ans++;
    FOR(i,1,N+1){
        D.at(i) = D.at(i-1) + L.at(i-1);
        if(D.at(i) <= X) ans++;
    }
    printf("%d\n",ans);

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main (void){
  	int n;
  	std::cin >> n;
	string str1,str2;
  	cin >> str1 >> str2;
  	string str;
	for(int i=0;i<n;++i){
    	cout << str1.at(i) << str2.at(i);
    }
return 0;
}


Measured memory_bytes: 256
//package Qe;

import java.io.*;
import java.util.*;
import java.util.Scanner;


public class Main {
    private static Scanner sc = new Scanner(System.in);
    private static int readInt() {return sc.nextInt();}
    private static String readWord() { return sc.next(); } 

    public static void main(String[] args) {
        int N = readInt();
        String S = readWord();

        SegTree[] sts = new SegTree[26];
        for (int i = 0; i<sts.length; i++) {
            sts[i] = new SegTree(N);
        }

        for (int i=0; i<N; i++) {
            sts[S.charAt(i) - 'a'].add(i, 1);
        }

        int Q = readInt();

        char[] ca = S.toCharArray();
        for (int q=0; q<Q; q++) {

            int type = readInt();
            String arg1 = readWord();
            String arg2 = readWord();

            switch (type) {
                case 1:
                    int I = Integer.parseInt(arg1) - 1;
                    char C = arg2.charAt(0);
                    if (ca[I] != C) {
                        sts[ca[I] - 'a'].add(I, -1);
                        sts[C - 'a'].add(I, 1);
                        ca[I] = C;
                    }
                    break;
                case 2:
                    int L = Integer.parseInt(arg1)-1;
                    int R = Integer.parseInt(arg2);
                    int ans = 0;
                    for (int i = 0; i<sts.length; i++) {
                        if (sts[i].sum(L, R) > 0) ans++;
                    }
                    System.out.println(ans);
                    break;
            }
        }
    }

    static class SegTree {
        private long[] sg;
        private long[] sg2;
        private int sz;
        private int N;

        public SegTree(int N) {
            this.N = N;
            int sz = 1;
            while (sz < N) {
                sz <<= 1;
            }
            this.sz = sz;
            sg = new long[sz << 1];
            sg2 = new long[sz << 1];
        }

        void add(int i, int j, long X, int v, int l, int r) {
            if (r <= i || j <= l) {
                return;
            }
            if (i <= l && r <= j) {
                sg2[v] += X;
            } else {
                sg[v] += (Math.min(j, r) - Math.max(i, l)) * X;
                int m = (l + r) / 2;
                add(i, j, X, v * 2 + 1, l, m);
                add(i, j, X, v * 2 + 2, m, r);
            }
        }

        void add(int i, long X) {
            add(i, i+1, X, 0, 0, this.sz);
        }

        long sum(int i, int j, int v, int l, int r) {
            if (r <= i || j <= l) {
                return 0L;
            } else if (i <= l && r <= j) {
                return sg[v] + (r - l) * sg2[v];
            } else {
                long base = (Math.min(j, r) - Math.max(i, l)) * sg2[v];
                int m = (l + r) / 2;
                long vl = sum(i, j, v * 2 + 1, l, m);
                long vr = sum(i, j, v * 2 + 2, m, r);
                return base + vl + vr;
            }
        }

        long sum(int i, int j) {
            return sum(i, j, 0, 0, this.sz);
        }
    }
}

Measured memory_bytes: 514236
s = list(input())
t = list(input())
n = len(s)
end = 0
alp = list("abcdefghijklmnopqrstuvwxyz")
for i in range(26):
    k = ""
    kk = ""
    for j in range(n):
        if t[j] == alp[i]:
            if k == "" or s[j] == k:
                k = s[j]
            else:
                end = 1
                break
        if s[j] == alp[i]:
            if kk == "" or t[j] == kk:
                kk = t[j]
            else:
                end = 1
                break
if end == 1:
    print("No")
else:
    print("Yes")

Measured memory_bytes: 8488
#include<bits/stdc++.h>
using namespace std;
vector<int> v;
int a,b,k;
void gcd(){
    int res=min(a,b);
    for(int i=1;i<=res;i++) if(a%i==0&&b%i==0){
        v.push_back(i);
    }
}
void Solve(){
    cin>>a>>b>>k;
    gcd();
    //for(int i=0;i<v.size();i++) cout<<v[i]<<" ";
    cout<<v[v.size()-k]<<endl;
}
int main(){
    Solve();
    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++)
using ll = long long;

int main()
{
    int n ;
    cin >> n ;
    int AC=0;
    int WA = 0 ;
    int TLE = 0 ;
    int RE = 0 ;

    string s ;
    rep(i,n)
    {
        cin >> s ;
        if(s=="AC")
        {
            AC++;
        }
        else if(s=="WA")
        {
            WA++ ;
        }
        else if(s=="TLE")
        {
            TLE++ ;
        }
        else
        {
            RE++ ;
        }

        
        
    }

    cout << "AC x " << AC << endl ;
        cout << "WA x " << WA << endl;
        cout << "TLE x " << TLE << endl;
        cout << "RE x " << RE << endl;
}

Measured memory_bytes: 3624
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <map>
#include <string>
#include <math.h>
#include <vector>
#include <cstdlib>
#include <queue>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define debug(x) cerr << x << " " \
                      << "(L:" << __LINE__ << ")" << '\n';

typedef long long ll;

using namespace std;

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

    string word;
    cin >> word;

    word[K - 1] = word[K - 1] + 32;

    cout << word << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
static const ll MAX = 1000000000000000;
static const int NIL = -1;
using namespace std;
const long double EPS = 0.0000000001;
const long double PI = (acos(-1));
const int MOD = 1000000007;

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

ll gcd(ll a, ll b) {
    if (a % b == 0) {
        return b;
    } else {
        return gcd(b, a % b);
    }
}

int main(){
    ll n,k; cin >> n >> k;
    bool flag1 = false,flag2 = false;
    vector<ll> a(n);

    rep(i,n){
        cin >> a[i];
        if(a[i] == k){
            flag1 = true;
            flag2 = true;
        }

        if(a[i] > k){
            flag1 = true;
        }
    }

    rep(i,n-1){
        ll tmp1 = abs(a[i]-a[i-1]);
        ll tmp2 = gcd(a[i],a[i+1]);
        if(k%gcd(tmp1,tmp2) == 0){
            flag2 = true;
        }

    }

    if(flag1 && flag2) cout << "POSSIBLE";
    else cout << "IMPOSSIBLE";

    return 0;
}

Measured memory_bytes: 4004
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

#define MAXN 200009

int l[MAXN], r[MAXN];

vector <int> v[MAXN];

int ult[MAXN];

int unde[MAXN], cine[MAXN];

struct lex_compare {
    bool operator () (const int &x, const int &y) const {
        return r[x] > r[y];
    }
};

multiset <int, lex_compare> s;

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        cin >> l[i] >> r[i];

    for (int i = 1; i <= n; i++)
        v[l[i]].push_back(i);

    for (int i = m; i > 0; i--) {
        for (auto &x : v[i])
            s.insert(x);

        if(!s.empty()) {
            int x = *(s.begin());
            s.erase(s.begin());

            cine[i] = x;
            unde[x] = i;
        }
    }

    int rest = 0;
    for (int i = 1; i <= m; i++) {
        if(cine[i]) {
            int x = cine[i];
            cine[i] = 0;
            unde[x] = i - rest;
            cine[unde[x]] = x;
        }else rest++;
    }

    int q = 0;
    for (int i = 1; i <= n; i++)
        if(unde[i] == 0)
            ult[++q] = r[i];

    std::sort(ult + 1, ult + q +1);

    int poz = 1;
    for (int i = 1; i <= m; i++)
        if(poz <= q && ult[poz] <= i && cine[i] == 0)
            poz++;

    int ans = q - poz + 1;
    cout << ans;

    return 0;
}


Measured memory_bytes: 18548
# いろいろ高速化
# https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8436413
class Rmq:
    # 平方分割
    # 値を変更すると元のリストの値も書き換わる
    # 検証: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3990681
    def __init__(self, a, sqrt_n=150, inf=(1<<31)-1):
        self.sqrt_n = sqrt_n
        if hasattr(a, "__iter__"):
            from itertools import zip_longest
            self.n = len(a)
            self.layer0 = [min(values) for values in zip_longest(*[iter(a)]*sqrt_n, fillvalue=inf)]
            self.layer1 = a
        elif isinstance(a, int):
            self.n = a
            self.layer0 = [inf] * ((a - 1) // sqrt_n + 1)
            self.layer1 = [inf] * a
        else:
            raise TypeError

    def get_min(self, l, r):
        sqrt_n = self.sqrt_n
        parent_l, parent_r = l//sqrt_n+1, (r-1)//sqrt_n
        if parent_l < parent_r:
            return min(min(self.layer0[parent_l:parent_r]),
                       min(self.layer1[l:parent_l*sqrt_n]),
                       min(self.layer1[parent_r*sqrt_n:r]))
        else:
            return min(self.layer1[l:r])

    def set_value(self, idx, val):
        self.layer1[idx] = val
        idx0 = idx // self.sqrt_n
        idx1 = idx0 * self.sqrt_n
        self.layer0[idx0] = min(self.layer1[idx1:idx1+self.sqrt_n])

    def chmin(self, idx, val):
        if self.layer1[idx] > val:
            self.layer1[idx] = val
            idx //= self.sqrt_n
            self.layer0[idx] = min(self.layer0[idx], val)

    def debug(self):
        print("layer0=", self.layer0)
        print("layer1=", self.layer1)

    def __getitem__(self, item):
        return self.layer1[item]

    def __setitem__(self, key, value):
        self.set_value(key, value)


from operator import itemgetter
def main():
    N, M, *LRC = map(int, open(0).read().split())
    LRC = list(zip(*[iter(LRC)]*3))
    LRC.sort(key=itemgetter(0))

    idx_LRC = 0
    q = []

    inf = 10**18
    seg = Rmq(N+1, inf=inf)

    seg.set_value(1, 0)
    for v in range(1, N + 1):
        d = seg.get_min(v, N + 1)
        while idx_LRC < M:
            l, r, c = LRC[idx_LRC]
            if l <= v:
                seg.chmin(r, d+c)
                idx_LRC += 1
            else:
                break
    ans = seg[N]
    print(ans if ans != inf else -1)

main()


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

int main(){

  int groop2[4] = {4, 6, 9, 11};
  int groop1[7] = {1, 3, 5, 7, 8, 10, 12};

  int x, y;
  cin>>x>>y;

  if (x==y){
    cout<<"Yes"<<endl; 
    return 0;
  }

  bool flagX , flagY;
  flagX = flagY = false;

  for(int i = 0; i < 7; i++){
    if (groop1[i] == x) flagX = true;
    if (groop1[i] == y) flagY = true;
  }

  if (flagX == true && flagY == true){
    cout<<"Yes"<<endl;
    return 0;
  }

  flagX = flagY = false;
  for (int i = 0; i < 4; i++){
    if (groop2[i] == x) flagX = true;
    if (groop2[i] == y) flagY = true;
  }

  if (flagX == true && flagY == true){
    cout<<"Yes"<<endl;
    return 0;
  }

  cout<<"No"<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(k,i,n) for(ll i=k;i<n;++i)
int main(void){
    ll n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    string s0=s.substr(k-1,1);
    if(s0=="A"){
        s0="a";
    }else if(s0=="B"){
        s0="b";
    }else{
        s0="c";
    }
    cout<<s.substr(0,k-1)<<s0<<s.substr(k,n-k);
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	int i,a[31]={0},s;
	for(i=0;i<28;i++){
		cin>>s;
		a[s]=1;
	}
	for(i=1;i<31;i++){
		if(a[i]==0){
			cout<<i<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3076
#include <stdio.h>
#include <stdlib.h>

#define INIT_CAP 10
#define INF 1000000000

typedef struct {
	int to, w;
} Edge;

typedef struct {
	Edge *elem;
	int cap, size;
} VecEdge;

typedef struct {
	int num;
	int d;
} PairNumDis;

typedef struct {
	int d;
	int idx;
} Node;

VecEdge adj[10000];
PairNumDis heap[10000];
int hsize;
Node node[10000];

void init(int n) {
	while (n--)
		adj[n] = (VecEdge){malloc(sizeof(Edge) * INIT_CAP), INIT_CAP, 0};
}

void add(int from, int to, int w) {
	if (adj[from].size == adj[from].cap) {
		adj[from].cap <<= 1;
		adj[from].elem = realloc(adj[from].elem, sizeof(Edge) * adj[from].cap);
	}
	adj[from].elem[adj[from].size++] = (Edge){to, w};
}

int calcNextIdx(int i) {
	return i * 2 + 1 + (i * 2 + 2 < hsize && heap[i * 2 + 1].d > heap[i * 2 + 2].d);
}

PairNumDis delete(void) {
	int i;
	int nextIdx;
	const PairNumDis root = heap[0], last = heap[--hsize];

	for (i = 0; i * 2 + 1 < hsize && last.d > heap[nextIdx = calcNextIdx(i)].d; i = nextIdx) {
		heap[i] = heap[nextIdx];
		node[heap[i].num].idx = i;
	}
	heap[i] = last;
	node[last.num].idx = i;

	return root;
}

void decreaseKey(int num, int d) {
	int i;

	for (i = node[num].idx; i > 0 && d < heap[i - 1 >> 1].d; i = i - 1 >> 1) {
		heap[i] = heap[i - 1 >> 1];
		node[heap[i].num].idx = i;
	}
	heap[i] = (PairNumDis){num, d};
	node[num].idx = i;
}

void dijkstra(int n, int s) {
	int i;

	for (i = 0; i < n; i++) {
		heap[i] = (PairNumDis){i, INF};
		node[i] = (Node){INF, i};
	}
	hsize = n;

	node[s].d = 0;
	decreaseKey(s, 0);
	while (hsize > 0) {
		PairNumDis fromPair = delete();
		for (i = 0; i < adj[fromPair.num].size; i++) {
			Edge e = adj[fromPair.num].elem[i];
			if (fromPair.d + e.w < node[e.to].d) {
				node[e.to].d = fromPair.d + e.w;
				decreaseKey(e.to, node[e.to].d);
			}
		}
	}
}

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

	scanf("%d", &n);

	init(n);
	for (i = 0; i < n; i++) {
		int u, k;
		scanf("%d %d", &u, &k);
		while (k--) {
			int v, c;
			scanf("%d %d", &v, &c);
			add(u, v, c);
			// add(v, u, c);
		}
	}

	dijkstra(n, 0);

	for (i = 0; i < n; i++)
		printf("%d %d\n", i, node[i].d);

	return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pll> vpl;

#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

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

  ll n;
  cin>>n;
  vll a(n);
  REP(i,n)cin>>a[i];

  bool flag = true;
  REP(i,n){
    if(a[i]%2==0){
      if(a[i]%3==0 || a[i]%5==0)
        ;
      else
        flag =  false;
    }
  }

  if(flag)
    cout<<"APPROVED"<<endl;
  else
    cout<<"DENIED"<<endl;
}


Measured memory_bytes: 256