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

int main() {
    string s;
    cin >> s;
    for (int i=0; i<s.size(); i++) {
        int j = i+1;
        if (j%2 == 0 && s[i] == 'R') {
            cout << "No";
            return 0;
        }
        if (j%2 == 1 && s[i] == 'L') {
            cout << "No";
            return 0;
        }

    }

    cout << "Yes";

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
ll MOD=1000000007;
ll mod=998244353;
int inf=1000000000;
ll INF=10000000000000000;


int main(){
    int a,b,c;
    cin >> a >> b >> c;
    if (b+c<=a) cout << 0 << endl;
    else cout << c-a+b << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <queue>
using namespace std;
typedef long long int ll;
typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
typedef pair<ll,ll> pairs;
vector<pairs> p;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
bool pairCompareSecond(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.second < secondElof.second;
}
#define MAX_N 100100
#define MOD 1000000007
bool x[MAX_N];
ll num[MAX_N];
ll fibl[MAX_N]={0};
// 四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll fib(ll a){
    if (fibl[a]!=0)return fibl[a];
    if (a==0){
        return 0;
    }else if (a==1){
        return 1;
    }
    return fibl[a]=fib(a-1)+fib(a-2);
}
 
ll eratosthenes(ll n) {
    int p = 0;
    for (ll i=0; i<=n; ++i) x[i] = true;
    x[0] = x[1] = false;
    for(int i=2; i<=n; ++i) {
        if(x[i]) {
            p++;
            for(int j=2*i; j<=n; j+=i) x[j] = false;
        }
        
        num[i] = p;
    }
    return p;
}
 
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}
 
ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

void  base_num(ll data,ll base){
    if(data==0) return;
    ll next=abs(data)%abs(base);
    if(data<0) next=(abs(base)-next)%abs(base);
    base_num((data-next)/base,base);
    cout << next;
}



int main(){
    ll n,ans=INF;
    string s;
    cin >> n >> s;
    ll a[n],b[n];
    a[0]=0;
    b[n-1]=0;
    if (s[0]=='W')a[0]=1;
    if (s[n-1]=='E')b[n-1]=1;
    for (ll i=1;i<n;i++){
        if (s[i]=='W'){
            a[i]=a[i-1]+1;
        }else{
            a[i]=a[i-1];
        }
    }
    for (ll i=n-2;i>=0;i--){
        if (s[i]=='E'){
            b[i]=b[i+1]+1;
        }else{
            b[i]=b[i+1];
        }
    }
    for (ll i=0;i<n;i++){
        ans=min(a[i]+b[i]-1,ans);
    }
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 5380
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[] s = br.readLine().split(" ",0);
	int K = Integer.parseInt(s[0]);
	int S = Integer.parseInt(s[1]);
	int X,Y,Z;
	int count = 0;
	for(X = 0; X <= K; X++){
	    for(Y = 0; Y <= K; Y++){
		Z = S - X - Y;
		if(0 <= Z && Z  <= K){
		    count++;
		}
	    }
	}
	System.out.println(count);
    }
}


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

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;

template <uint MD> struct ModInt {
    using M = ModInt;
    uint v;
    ModInt() : v(0) {}
    ModInt(ll _v) { set_v(_v % MD + MD); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(ull(v) * r.v % MD); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<TEN(9) + 7>;
const int MN = 2 * TEN(7) + TEN(6);
V<Mint> fact(MN + 1), iFac(MN + 1);
void first() {
    fact[0] = Mint(1);
    for (int i = 1; i <= MN; i++) fact[i] = fact[i-1] * i;
    iFac[MN] = fact[MN].inv();
    for (int i = MN; i >= 1; i--) iFac[i-1] = iFac[i] * i;
    assert((fact[114]*iFac[114]).v == 1);
}
Mint C(int n, int k) {
    if (n < k || k < 0) return Mint(0);
    return fact[n] * iFac[k] * iFac[n-k];
}
Mint iC(int n, int k) {
    if (n < k || k < 0) return Mint(0);
    return iFac[n] * fact[k] * fact[n-k];
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(20) << fixed;
    first();
    int h, w, k;
    cin >> h >> w >> k;
    Mint ans = Mint(k);
    Mint buf1 = 0, buf2 = 0;
    for (int i = 1; i <= k; i++) {
        buf1 += C(h + w - 2, i - 2) * iC(h + w, i);
        buf2 += C(h + w - 1, i - 1) * iC(h + w, i);
    }
    ans += Mint(h) * Mint(w) * buf1;
    ans += (Mint(h) + Mint(w)) * buf2;
    ans *= fact[h + w] * iFac[h + w - k];
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 164352
#include <bits/stdc++.h>
const double PI = acos(-1);
#define rep(i, n) for (int i = 0; i < (int)(n); i++ )
using namespace std;
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}
int main(){
    int n;
    cin >> n;
    bool ans = false;
    rep(i,3){
        if(n % 10 == 7){
            ans = true;
            break;
        }
        n /= 10;
    }
    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3564
fn main() {
    let n = read::<usize>();
    let mut ret = 0;
    for i in 1..n+1 {
        if i % 3 == 0 && i % 5 == 0 {
            
        } else if i % 3 == 0 {
            
        } else if i % 5 == 0 {
            
        } else {
            ret += i;
        }
    }

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

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().parse().ok().unwrap()
}

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

#ifdef LOCAL
#define debug(var) cerr << (#var) << " = " << (var) << endl;
#else
#define debug(var)
#endif

void init() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}

const int mod = 1e9+7;

long long binpow(long long b, long long e) {
  if (!e) return 1;
  if (e&1) return b*binpow(b, e-1)%mod;
  return binpow(b*b%mod, e/2);
}

const int N = 1e5+23;

long long dp[N];

void solve() {
  int n, k; scanf("%d%d", &n, &k);
  
  long long ans = 0;
  for (int i = k; i >= 1; --i) {
    dp[i] = binpow(k/i, n);
    for (int j = i+i; j <= k; j += i) {
      dp[i] = (dp[i] - dp[j] + mod) % mod;
    }
    ans = (ans + dp[i]*i%mod) % mod;
  }
  printf("%lld", ans);
}

int main() {
  init();
  int t = 1; //scanf("%d", &t);
  while (t--) {
    solve();
  }
  return 0;
}


Measured memory_bytes: 4540
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
#define Mod 1000000007
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;

char itoc(ll c){
    if(c==0) return 'A';
    else if(c==1) return 'G';
    else if(c==2) return 'C';
    else return 'T';
}

string itos(ll p){
    string s="";
    for(ll i=0;i<3;i++){
        s+=itoc(p%4);
        p=p/4;
    }
    return s;
}
 

int main(){
    ll i,j;
    ll n;
    cin>>n;
    VVI dp(n,VI(64,0));
    for(i=0;i<64;i++){
        if(itos(i)!="AGC"&&itos(i)!="GAC"&&itos(i)!="ACG"){
            dp[2][i]=1;
        }
    }
    for(i=3;i<n;i++){
        for(j=0;j<64;j++){
            for(ll k=0;k<4;k++){
                bool f=1;
                string  w=itos(j/4 + 16*k);
                if(w=="AGC"||w=="GAC"||w=="ACG") f=0;
                string ho=itos(j);
                if(ho[0]=='A'&&itoc(k)=='C'){
                    if(ho[1]=='G'||ho[2]=='G') f=0;
                }

                if(f){
                    dp[i][j/4+16*k]+=dp[i-1][j];
                    dp[i][j/4+16*k]%=Mod;
                }
            }

        }
    }

    ll ans=0;
    for(i=0;i<64;i++){
        ans+=dp[n-1][i];
        
        ans%=Mod;
    }
    cout<<ans<<endl;


    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
priority_queue<ll> que[4];
vector<ll> vec[4];
ll N, W, w, v, w1, d[4][110], res;

void dfs(ll x, ll y, ll z){
    if (x == 4) {
        if (z > W) return;
        res = max(res, y);
    } else {
        for (ll i = 0; i <= vec[x].size(); i++) {
            dfs(x + 1, y + d[x][i], z + i * (w1 + x));
        }
    }
}

int main(void){
    // Your code here!
    cin >> N >> W >> w1 >> v;
    vec[0].push_back(v);
    for (ll i = 1; i < N; i++) {
        cin >> w >> v;
        vec[w - w1].push_back(v);
    }
    for (ll i = 0; i < 4; i++) {
        sort(vec[i].begin(), vec[i].end());
        reverse(vec[i].begin(), vec[i].end());
    }
    for (ll i = 0; i < 4; i++) {
        for (ll j = 1; j <= vec[i].size(); j++) {
            d[i][j] = d[i][j - 1] + vec[i][j - 1];
        }
    }
    dfs(0, 0, 0);
    cout << res << endl;
}


Measured memory_bytes: 256
def main():
    x = int(input())
    a = 1
    b = 1
    
    for i in range(-118, 120):
        a = i
        for j in range(-118, 120):
            b = j
            if x == a**5 - b**5:
                ans = str(a) + ' ' + str(b)
                print(ans)
                return


if __name__ == '__main__':
    main()

Measured memory_bytes: 9092
#include <ios>
#include <iomanip>
#include <iostream>
#include <functional>
#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>
#include <climits>

using namespace std;
typedef long long int ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e9)
#define PI (acos(-1))
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl

ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
typedef pair <ll,ll> P;

int main()
{
    ll N, M;
    cin >> N >> M;
    vector<P> stu(N);
    rep(i, N) {
        ll a, b;
        cin >> a >> b;
        stu[i] = make_pair(a, b);
    }
    vector<P> pos(M);
    rep(i, M) {
        ll c, d;
        cin >> c >> d;
        pos[i] = make_pair(c,d);
    }
    rep(i, N) {
        ll mind = MOD;
        rep(j, M) {
            mind = min(mind, abs(pos[j].first - stu[i].first) + abs(pos[j].second - stu[i].second)); 
        }
        rep(j, M) {
            if (mind == abs(pos[j].first - stu[i].first) + abs(pos[j].second - stu[i].second)) {
                print(j+1);
                break;
            }
        }
    }
    return 0;
}


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

int main() {
    int n;
    cin >> n;
    int min;
    
    for (int i = 0; i < n; i++) {
        long a;
        cin >> a;
        
        int count = 0;
        while (a % 2 == 0) {
            count += 1;
            a /= 2;
        }
        
        if (i == 0) min = count;
        else if (count < min) min = count;
    }
    
    cout << min << endl;
}


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

int main(){
  int r,D,x;
  cin >> r >> D >> x;
  
  rep(i,10){
    x = r*x - D;
    cout << x << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
int main(){
	long long int a,b;
	while(1){
		cin>>a>>b;
		if(a==0&&b==0)break;
		if(a<b)swap(a,b);
		int cnt=0;
		while(1){
			a%=b;
			swap(a,b);
			cnt++;
			if(b==0)break;
		}
		cout<<a<<" "<<cnt<<endl;
	}
}

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N,T;
int t[222222];

signed main(){
    cin>>N>>T;
    rep(i,N)cin>>t[i];

    int cur=0;
    int ans=0;
    while(cur<N){
        int nex=cur;
        while(nex+1<N&&t[nex+1]-t[nex]<=T)nex++;
        ans+=t[nex]-t[cur]+T;
        cur=nex+1;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1792
while True:
    n = input()
    if n == 0:
        break
    else:
        a = 0
        b = 0
        for i in range(n):
            lst = raw_input().split(' ')
            if lst[0] > lst[1]:
                a += int(lst[0]) + int(lst[1])
            elif lst[0] < lst[1]:
                b += int(lst[0]) + int(lst[1])
            else:
                a += int(lst[0])
                b += int(lst[1])
        print str(a) + ' ' + str(b)


Measured memory_bytes: 4524
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

type edge struct {
	to, cost int
}

var node [100100][]edge
var cost [100100]int
var used [100100]bool

func dfs(n, c int) bool {
	used[n] = true
	cost[n] = c
	for _, e := range node[n] {
		if used[e.to] == true {
			if c+e.cost != cost[e.to] {
				return false
			}
			continue
		}
		flg := dfs(e.to, c+e.cost)
		if flg == false {
			return false
		}
	}
	return true
}

func main() {
	sc.Split(bufio.ScanWords)
	N, M := getInt(), getInt()

	for i := 0; i < M; i++ {
		l, r, d := getInt()-1, getInt()-1, getInt()
		node[l] = append(node[l], edge{r, d})
		node[r] = append(node[r], edge{l, -d})
	}

	// out(node[:10], N, M)

	ans := true
	for i := 0; i < N; i++ {
		flg := true
		if used[i] == false {
			flg = dfs(i, 0)
			// out(flg)
		}
		if flg == false {
			ans = false
			break
		}
	}
	if ans {
		out("Yes")
	} else {
		out("No")
	}
}


Measured memory_bytes: 38528
#include<bits/stdc++.h>
#define ll long long
#define gcd(x,y) __gcd(x,y)
#define fi first
#define se second
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
template <class A> inline ll abs(A &a) { return (a < 0 ? -a : a); }
using namespace std;
const ll inf=(1LL<<62);
const ll MOD=(1e9)+7;
const ll mod=998244353;
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
    string s;
    cin >> s;
    int n = s.size();
    if (s[n - 1] == 's') {
      cout << s;
      cout << "es\n";
    }else{
      cout << s;
      cout << "s\n";
    }
  return 0;
}


Measured memory_bytes: 3656
#alds1_5_a


def exhaustive_search(m, i):
    global solved
    global A
#    if solved[m][i] is not None:
#        return solved[m][i]

    if A[i] == m:
        solved[m][i] = True
        return True

    if (i + 1) < len(A):
        return exhaustive_search(m - A[i], i+1) or exhaustive_search(m, i+1)
    else:
        solved[m][i] = False
        return False
    

if __name__ == "__main__":
    n = int(input())
    A = sorted(map(int, input().split()))
    q = input()
    solved = [[None for i in range(n)] for j in range(2000)]

    for m in map(int, input().split()):
        if sum(A) < m:
            print('no')
        elif exhaustive_search(m, 0):
            print('yes')
        else:
            print('no')


Measured memory_bytes: 6144
#include <iostream>
//using namespace System;

int main()
{
    int d;
	while(std::cin>>d){
		int ans=0;
		for(int i=1;i<600/d;i++){
			ans+=i*d*i*d*d;
		}
		std::cout<<ans<<std::endl;
	}
    return 0;
}

Measured memory_bytes: 1160
#include <iostream>
using namespace std;
#define MAX 100001
#define SENTINEL 2000000000
struct Card { char suit; int val; };
Card L[MAX / 2 + 2], R[MAX / 2 + 2];

void merge(struct Card B[], int left,int mid, int right) {
	int i, j,n1,n2,k;
	
	n1 = mid - left;
	n2 = right - mid;
	for (i = 0; i < n1; i++){L[i] = B[left + i];}
	for (i = 0; i < n2; i++){R[i] = B[mid + i];}
	L[n1].val=R[n2].val=SENTINEL;
	i = j = 0;
	for (k = left; k < right; k++) {
		if (L[i].val <= R[j].val){B[k] = L[i++];}
		else {B[k] = R[j++];}
	}


}
void mergesort(struct Card B[], int left, int right) {
	if (right > left+1) {
		int mid;
		mid = (right + left) / 2;
		mergesort(B, left, mid);
		mergesort(B, mid, right);
		merge(B, left, mid, right);
	}
}

void quicksort(struct Card A[], int a, int b) {	
	if (b > a) {
		int i, j, v;
		j = a;
		v = A[b].val;
		for (i = a; i <= b; i++) { if (A[i].val <= v)swap(A[i], A[j++]); }
		quicksort(A, a, j - 2);
		quicksort(A, j, b);
	}
}
int main(void) {
	int i, n,flag=1;
	Card A[MAX],B[MAX];
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> A[i].suit >> A[i].val;
		B[i].suit = A[i].suit; B[i].val = A[i].val;
	}
	quicksort(A, 0, n - 1);
	mergesort(B, 0, n);

	for (i = 0; i < n; i++) {
	    if(A[i].suit!=B[i].suit)flag=0;
	}
	flag==0? cout<<"Not stable"<<endl: cout<<"Stable"<<endl;
		for (i = 0; i<n; i++) {
		cout << A[i].suit <<" "<< A[i].val <<endl;}
	return 0;
}

Measured memory_bytes: 5428
#![allow(
    non_snake_case,
    unused_variables,
    unused_assignments,
    unused_mut,
    unused_imports,
    dead_code
)]
//use permutohedron::LexicalPermutation as _;
use proconio::input;
//use proconio::marker::*;
//use std::collections::*;
use std::cmp::*;
// use std::num;
fn main() {
    input! {N:usize, A:[i64;N]}
    let inf = std::i64::MIN / 4;
    let mut ans = inf;
    let mut dp = vec![vec![inf; 3]; N + 1];
    // dp[i][j] i個まで進めた時、スキップ消費済みの数をjとする。
    // Nが奇数なら、最終的にスキップを2個消費する
    // Nが偶数なら、最終的にスキップを1個消費する
    let k = N % 2 + 1;
    dp[0][0] = 0;
    for i in 0..N {
        if i % 2 == 0 {
            // 偶数個 なら、奇数番目は…。
            dp[i + 1][0] = dp[i][0] + A[i];
            dp[i + 1][1] = max(dp[i][0], dp[i][1]);
            dp[i + 1][2] = dp[i][2] + A[i];
        } else {
            dp[i + 1][0] = dp[i][0];
            dp[i + 1][1] = dp[i][1] + A[i];
            dp[i + 1][2] = max(dp[i][1], dp[i][2]);
        }
    }
    //println!("{:?}", dp);
    let ans = max(dp[N][k - 1], dp[N][k]);
    println!("{}", ans);
}


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

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i <= (ll)(n); i++)
#define INF 10000000000
#define MOD 10007
using ll = long long;
using Graph = vector<vector<int>>;

int main(){
  ll N,H; cin>>N>>H;
  vector<tuple<ll,char,int>> katana;
  rep(i,N){
    ll a,b; cin>>a>>b;
    katana.push_back(make_tuple(a,'a',i+1));
    katana.push_back(make_tuple(b,'b',i+1));
  }
  sort(katana.begin(),katana.end());
  reverse(katana.begin(),katana.end());
  ll res = 0;
  rep(i,2*N+10){
    if(get<1>(katana.at(i))=='a'){
      ll tmp = get<0>(katana.at(i));
      res+=((H-1)/tmp+1);
      cout<<res<<endl;
      return 0;
    }else{
      H-=get<0>(katana.at(i));
      res++;
    }
    if(H<=0)break;
  }   
  cout<<res<<endl;
}


Measured memory_bytes: 6512
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>

using namespace std;
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REPR(i,n) for(int i=(n)-1;i>=0;i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());
#define PAU system("pause")

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 28);
const double PI = acos(-1);

//解説AC

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	string S;
	cin >> S;
	if (SZ(S) < 26) {
		vb B(26, true);
		REP(i, SZ(S)) {
			B[S[i] - 'a'] = false;
		}
		REP(i, 26) {
			if (B[i]) {
				cout << S << (char)('a' + i) << endl;
				break;
			}
		}
	}
	else {
		int ind = 0;
		REPR(i, 26) {
			if (i - 1 < 0) {
				cout << -1 << endl;
				PAU;
				return 0;
			}
			ind = i;
			if (S[i - 1] < S[i]) {
				break;
			}
		}
		char c = 'z'+1;
		FOR(i, ind, 26) {
			if (S[i] > S[ind - 1])c = min(c, S[i]);
		}
		cout << S.substr(0, ind - 1) << (char)c << endl;
	}
	PAU;
	return 0;
}


Measured memory_bytes: 504
#include "bits/stdc++.h"
using namespace std;
#define fios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
typedef long long ll;
#ifdef LOCAL
mt19937 rng(unsigned(70));
#else
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#endif
#define rand rng


int main() {
	// fios;
	ll n , k;
	cin >> n >> k;
	vector<ll> a(n);
	for(auto &x: a) {
		cin >> x;
	}

	vector<ll> cyc;
	unordered_map<ll, ll> mp;
	cyc.push_back(1);
	mp[1]++;
	ll i = a[0];
	ll cyclen = 0, tail = 0;
	while(1) {
		if(mp.find(i) != mp.end()) {
			break;
		}
		mp[i]++;
		cyc.push_back(i);
		i = a[i-1];
	}
	ll j = 0;
	for(; j < (ll)cyc.size(); j++) {
		if(cyc[j] == i) {
			cyclen = (ll) cyc.size() - j;
			break;
		}
	}
	tail = j;
	if(k < tail) cout << cyc[k] << endl;
	else {
		k -= tail;
		cout << cyc[tail + k % cyclen] << endl;
	}


}

Measured memory_bytes: 14408
import math

a, b, x = map(int, input().split())
s_all = (a ** 2) * b
if x <= s_all / 2:
    tmp = (a * b ** 2) / (2 * x)
    tan = math.atan(tmp)
else:
    tmp = 2 * (s_all - x) / (a ** 3)
    tan = math.atan(tmp)
print(math.degrees(tan))


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
#define forn(i,n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef long long i64;
typedef long double ld;
const int inf = int(1e9) + int(1e5);
const ll infl = ll(2e18) + ll(1e10);

const int maxn = 500100;

int n;
char s[maxn];

int to[maxn][26];
int ze[maxn];

int calcTo(int i, int c) {
    //cerr << "to " << i << ' ' << c << "\n";
    int &res = to[i][c];
    if (i >= n)
        return res = inf;
    int d = s[i] - 'a';
    if (d == c) {
        return res = i + 1;
    } else if (d > c) {
        if (ze[i] == inf)
            return res = inf;
        return res = to[ze[i]][c];
    } else {
        res = i + 1;
        for (int ch = d; ch < c; ++ch) {
            res = to[res][ch];
            if (res == inf)
                break;
        }
        return res;
    }
}

int calcZe(int i) {
    //cerr << "ze " << i << "\n";
    int &res = ze[i];
    if (i >= n)
        return res = inf;
    int d = s[i] - 'a';
    res = i + 1;
    for (int ch = d; ch < 26; ++ch) {
        res = to[res][ch];
        if (res == inf)
            break;
    }
    return res;
}

vector<int> g[maxn];
bool used[maxn];
int in[maxn];
int out[maxn];
int timer;

void dfs(int u) {
    in[u] = timer++;
    used[u] = true;
    for (int v: g[u]) {
        assert(!used[v]);
        dfs(v);
    }
    out[u] = timer;
}

bool pr(int u, int v) {
    return in[u] <= in[v] && out[v] <= out[u];
}

int main() {
    #ifdef LOCAL
    assert(freopen("c.in", "r", stdin));
    #else
    #endif
    int q;
    scanf("%s%d", s, &q);
    n = strlen(s);
    for (int i = n; i >= 0; --i) {
        calcZe(i);
        forn (j, 26) {
            calcTo(i, j);
        }
    }
    forn (i, n + 1) {
        int p = ze[i];
        //cerr << p << ' ' << i << '\n';
        assert(p > i);
        if (p <= n)
            g[p].push_back(i);
    }
    for (int i = n; i >= 0; --i)
        if (!used[i])
            dfs(i);

    forn (i, q) {
        int l, r;
        scanf("%d%d", &l, &r);
        --l;
        if (pr(r, l))
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}


Measured memory_bytes: 93440
#include<iostream>
using namespace std;
int n,k,a[300007];
struct madoka{
	int l;
	int r;
	int z;
}ma[3000007];
void build(int l,int r,int k){
	ma[k].l=l;
	ma[k].r=r;
	if(l==r){
		ma[k].z=0;
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,k*2);
	build(mid+1,r,k*2+1);
}
int qry(int k,int l,int r){
	if(l<=ma[k].l&&ma[k].r<=r){
		return ma[k].z;
	}
	int mid=(ma[k].l+ma[k].r)/2,ans1=0,ans2=0;
	if(l<=mid){
		ans1=qry(k*2,l,r);
	}
	if(mid<r){
		ans2=qry(k*2+1,l,r);
	}
	return max(ans1,ans2);
}
void up(int k,int p,int z){
	if(ma[k].l==ma[k].r){
		ma[k].z=z;
		return;
	}
	int mid=(ma[k].l+ma[k].r)/2;
	if(p<=mid){
		up(k*2,p,z);
	}
	else{
		up(k*2+1,p,z);
	}
	ma[k].z=max(ma[k*2].z,ma[k*2+1].z);
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		a[i]++;
	}
	build(1,300001,1);
	int ans=0,now=0;
	for(int i=1;i<=n;i++){
		now=qry(1,max(1,a[i]-k),min(a[i]+k,300001));
		ans=max(ans,now+1);
		up(1,a[i],now+1);
	}
	printf("%d\n",ans);
}


Measured memory_bytes: 17220
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define rep(i, a, n) for (ll i = (a); i < (n); i++)
#define debug(x) cerr << #x << ": " << x << endl;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

int main() {
    ll n;
    cin >> n;
    vector<ll> v(5);
    rep(i, 0, 5) cin >> v[i];
    sort(v.begin(), v.end());
    ll vmin = v[0];
    ll ans = 5 + (n+vmin-1)/vmin - 1;
    cout << ans << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Text;
using static System.Console;

namespace ABC123A
{
    static class Program
    {
        static void Main(string[] args)
        {
            var l = ReadLineOne<int>(5);
            var k = ReadLine().TryParse<int>();

            string a = l[4] - l[0] <= k ? "Yay!" : ":(";
            WriteLine(a);
        }


        public static T TryParse<T>(this String input)
        {
            try
            {
                var converter = TypeDescriptor.GetConverter(typeof(T));
                if (converter != null)
                {
                    return (T)converter.ConvertFromString(input);
                }
                else
                {
                    throw new InvalidCastException("");
                }
            }
            catch
            {
                throw new InvalidCastException(typeof(T) + " is not supported.");
            }
        }

        public static List<T> SplitTryParseToList<T>(this String input)
        {
            return input.Split().Select(n => n.TryParse<T>()).ToList();
        }

        public static List<T> ListSwap<T>(this List<T> list, Int32 index1, Int32 index2)
        {
            var t = list[index1];
            list[index1] = list[index2];
            list[index2] = t;
            return list;
        }

        public static List<Tuple<T, int>> DuplicateCount<T>(this IEnumerable<T> list)
        {
            return list
                .GroupBy(i => i)
                .Where(g => g.Any())
                .Select(g => Tuple.Create(g.Key, g.Count()))
                .ToList();
        }
        public static List<Tuple<T, int>> DuplicateSort<T>(this IEnumerable<Tuple<T, int>> list)
        {
            return list.OrderByDescending((x) => x.Item2).ToList();
        }
        public static List<T> ReadLineOne<T>(int n)
        {
            var list = new List<T>();
            foreach (var i in Enumerable.Range(1, n))
            {
                list.Add(Console.ReadLine().TryParse<T>());
            }
            return list;
        }
        public static void PrintAll<T>(this IEnumerable<T> list)
        {
            foreach (var i in list)
            {
                Console.Write($"{i} ");
            }

            Console.WriteLine();
        }
    }
}


Measured memory_bytes: 12384
#  from pprint import pprint
n = int(input())
a = map(int, input().split())
a = sorted(((ax, x) for x, ax in enumerate(a)), reverse=True)
dp = [[-1] * (n+1) for _ in range(n+1)]
dp[0][0] = 0
for i, (ax, x) in enumerate(a):
    for j in range(i+1):
        dp[j+1][i-j] = max(dp[j+1][i-j], dp[j][i-j] + ax*abs(x-j))
        dp[j][i-j+1] = max(dp[j][i-j+1], dp[j][i-j] + ax*abs(n-1-x-i+j))
# pprint(dp)
print(max(dp[i][n-i] for i in range(n+1)))


Measured memory_bytes: 105968
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#include<regex>
#include<bitset>
#include<chrono>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;
 
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;
}
 
using namespace std;
 
template <typename A, typename B>
string to_string(pair<A, B> p);
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
 
string to_string(const string& s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
 
void debug_out() { cerr << "\n"; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " <<to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

void solve(){
  string s,t;
  cin>>s>>t;
  cout<<t+s<<"\n";
}
 
int main(){
	ios::sync_with_stdio(false);
  cin.tie(0);
	cout<<fixed<<setprecision(15);
	solve();
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define all(v) v.begin(), v.end()
#define sz(v) v.size()
#define INF 100000000000000 //10^14
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
int main()
{
    ll N;
    string c;
    cin >> N >> c;
    ll ans = 0;
    vector<ll> wp(0), rp(0);
    rep(i, N){
        if(c.at(i) == 'W'){
            wp.push_back(i);
        }
        else{
            rp.push_back(i);
        }
    }
    reverse(all(rp));
    if(sz(wp) == 0 || sz(rp) == 0){
        cout << 0 << endl;
        return 0;
    }
    ll noww = 0;
    ll nowr = 0;
    while(wp.at(noww) < rp.at(nowr)){
        ans++;
        noww++;
        nowr++;
        if(noww >= sz(wp) || nowr >= sz(rp)){
            break;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 5728
const char* version[]=
{
	"+---------version--------------+",
	"+last update:2014/10/27/16:24  +",
	"+author:Takayuki Maruyama      +",
	"+------------------------------+",
	"endl"
};
const char* help[]=
{
	"+--------help----------------------------------+",
	"+summary:Baseball Simulation                   +",
	"+required inputs (stdin):                      +",
	"first line:inning count others:inning data     +",
	"+supported comandline options:-h -v            +",
	"+----------------------------------------------+",
	"endl"
};
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
//#define NDEBUG

void manage_helpAndVersionOutput(char arg_line[]);
void baseball_simulation();

int main(int argc, char* argv[])
{
	manage_helpAndVersionOutput(argv[argc-1]);
	

	int inning_count;
	scanf("%d",&inning_count);
	
	int inning=0;
	while(++inning<=inning_count)
	{
		baseball_simulation();
	}
	
	return 0;
}

void baseball_simulation()
{
	int out_count=0;
	int runner[4]={}; /*runner[3]には得点を格納*/
	char result[8];
	int base_count;
	while(out_count<3)
	{
		for(;1;)/*入力*/
		{
			fgets(result,sizeof(result),stdin);
			if(result[0]!='\n' && result[0]!='\r')
			{
				break;
			}
		}
		if(strstr(result,"HIT"))
		{
			for(base_count=2;base_count>=0;base_count--)/*ランナーの塁を進める*/
			{
				if(runner[base_count]==1)
				{
					runner[base_count]=0;
					runner[base_count+1]++;
				}
			}
			runner[0]++;/*打った人の出塁*/
		}
		else if(strstr(result,"HOMERUN"))
		{
			for(base_count=2;base_count>=0;base_count--)/*ランナーの得点*/
			{
				if(runner[base_count]==1)
				{
					runner[base_count]=0;
					runner[3]++;
				}
			}
			runner[3]++;/*打った人の得点*/
		}
		else if(strstr(result,"OUT"))
		{
			out_count++;
		}
		else
		{
			assert(!strcmp(result,"HIT") || !strcmp(result,"OUT") || !strcmp(result,"HOMERUN") && "unexpected input");
		}
	}
	printf("%d\n",runner[3]);
}
void manage_helpAndVersionOutput(char arg_line[])
{
	int line;
	if(strcmp(arg_line,"-h")==0)
	{
		for(line=0;strcmp(help[line],"endl");line++)
		{
			printf("%s\n",help[line]);
		}
		exit(0);
	}
	else if(strcmp(arg_line,"-v")==0)
	{
		for(line=0;strcmp(version[line],"endl");line++)
		{
			printf("%s\n",version[line]);
		}
		exit(0);
	}
}

Measured memory_bytes: 608
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<algorithm>
#include<utility>
#include<map>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
const int INF = 1001001001;

ll pow_mod(ll p, ll n, ll m) {
	if (n == 0) return 1;
	else if (n == 1) return p % m;
	else if (n % 2 == 1) return p * pow_mod(p, n - 1, m) % m;
	else {
		ll tmp = pow_mod(p, n / 2, m);
		return (tmp * tmp) % m;
	}
}

ll gcd(ll x, ll y) {
	if (y == 0) {
		return x;
	}
	return gcd(y, x % y);
}

ll com_mod(ll n, ll k, ll m) {
	if (k == 0) return 1;
	else {
		ll x = 1;
		ll y = 1;
		for (ll i = 0; i < k; i++) {
			x = (x * (n - i)) % m;
			y = (y * (i + 1)) % m;
		}
		ll res = (x * pow_mod(y, m - 2, m)) % m;
		return res;
	}
}

int main() {
	int a, b; cin >> a >> b;
	if (a + b < 10)cout << a + b << endl;
	else cout << "error" << endl;
	return 0;
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
#define ll long long
#define lsb(x) (x & -x)

using namespace std;

const ll INF = 1000000000 * 200005;

struct Data {
    ll cost;
    int l, r;
};

struct AINT {
    vector<ll> aint, lazy;

    AINT(int n) {
        aint.resize(n * 4 + 1, 0);
        lazy.resize(n * 4 + 1, 0);
    }

    void update(int from, int to, ll toadd, int node, int le, int ri) {
        if(from <= le && ri <= to) {
            lazy[node] += toadd;
            aint[node] += toadd;
        } else {
            int mid = (le + ri) / 2;
            if(from <= mid)
                update(from, to, toadd, node * 2, le, mid);
            if(mid < to)
                update(from, to, toadd, node * 2 + 1, mid + 1, ri);

            aint[node] = lazy[node] + max(aint[node * 2], aint[node * 2 + 1]);
        }
    }

    ll query(int from, int to, int node, int le, int ri) {
        if(from <= le && ri <= to)
            return aint[node];
        int mid = (le + ri) / 2;
        ll ans = -INF;
        if(from <= mid)
            ans = query(from, to, node * 2, le, mid);
        if(mid < to)
            ans = max(ans, query(from, to, node * 2 + 1, mid + 1, ri));
        ans += lazy[node];

        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);

    int n, m;
    cin >> n >> m;
    vector<Data> v(m + 1, {0, 0, 0});
    vector<ll> start(n + 2, 0);
    vector< vector<pair<int, int>> > en(n + 1);
    for(int i = 1; i <= m; i ++) {
        cin >> v[i].l >> v[i].r >> v[i].cost;
        start[v[i].l] += v[i].cost;
        en[v[i].r].push_back({v[i].l, v[i].cost});
    }

    n ++;
    vector<ll> dp(n + 1, 0);
    AINT aint(n);
    for(int i = 1; i <= n; i ++) {
        aint.update(0, i - 1, start[i], 1, 0, n);
        for(auto it : en[i - 1])
            aint.update(0, it.first - 1, -it.second, 1, 0, n);

        dp[i] = aint.query(0, i - 1, 1, 0, n);
        aint.update(i, i, dp[i], 1, 0, n);
    }

    cout << dp[n];

    return 0;
}


Measured memory_bytes: 29952
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int MAXN=300010;

int n, m, q, u, v, x, y, t, r, mod;
int par[MAXN];
int A[MAXN], B[MAXN], C[MAXN], G, Z;
bool good[1000000];

int getpar(int x){ return (par[x]==x?x:par[x]=getpar(par[x]));}
inline void join(int x, int y){ par[getpar(x)]=getpar(y);}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	iota(par, par+MAXN, 0);
	cin>>n>>m>>q>>mod;
	for (int i=1; i<=m; i++) cin>>A[i]>>B[i]>>C[i], G=__gcd(G, C[i]-C[1]);
	G=__gcd(G, mod);
	if (G<0) G*=-1;
	mod=__gcd(mod, 3*G);
	Z=C[1]%G;
	for (int i=1; i<=m; i++){
		int u=A[i], v=B[i], c=C[i];
		for (int s:{0, 1, 2}) for (int t:{0, 1}){
			join(u*6 + 2*s + t, v*6 + 2*((2*s+c/G)%3) + (t^1));
			join(v*6 + 2*s + t, u*6 + 2*((2*s+c/G)%3) + (t^1));
		}
	}
	int val=Z;
	while (!good[val]){
		good[val]=1;
		val=val*4%mod;
	}	
	
	while (q--){
		cin>>u>>v>>r;
		bool ans=0;
		for (int s:{0, 1, 2}) for (int t:{0, 1}) if (getpar(6*v)==getpar(6*u + 2*s + t)){
			int R=(r+Z-s*G)%mod;
			if (R<0) R+=mod;
			if (t) R=R*(mod+1ll)/2%mod;
			ans|=good[R];
		}
		cout<<(ans?"YES\n":"NO\n");
	}
	
	return 0;
}


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

ll n;

int main(void){
	scanf("%lld",&n);
	int ans=114514;
	for(ll i=1;i*i<=n;i++){
		ll j=n/i;
		if(i*j!=n)continue;
		ll v=i;
		int cnt=0;
		while(v>0LL){
			v/=10LL;
			cnt++;
		}
		int cnt2=0;
		v=j;
		while(v>0LL){
			v/=10LL;
			cnt2++;
		}
		ans=min(ans,max(cnt,cnt2));
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(int argc, char const *argv[]) {
  int h,w;
  cin>>h>>w;
  char a[h+2][w+2];
  for(int i=0;i<w+2;i++){
    a[0][i]='#';
    a[h+1][i]='#';
  }
  for(int i=1;i<h+1;i++){
    a[i][0]='#';
    a[i][w+1]='#';
  }
  for(int i=1;i<h+1;i++){
    for(int j=1;j<w+1;j++){
      cin>>a[i][j];
    }
  }
  for(int i=0;i<h+2;i++){
    for(int j=0;j<w+2;j++){
      if(j==w+1){
        cout<<a[i][j]<<endl;
      }else{
        cout<<a[i][j];
      }
    }
  }
  return 0;
}


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

int main()
{
  int a,b,c;
  cin >> a >> b >> c;
  if(a == b){
    if(b!=c){
      cout << "Yes" << endl;
    }
    else
      cout << "No" << endl;
  }
  else if(a == c){
    if(b!=c){
      cout << "Yes" << endl;
    }
    else
      cout << "No" << endl;
  }
  else if(c == b){
    if(a!=c){
      cout << "Yes" << endl;
    }
    else
      cout << "No" << endl;
  }
  else{
    cout << "No" << endl;
  }
  return 0;
}

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

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define MOD (1000000007)
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define pli pair<ll, int>a
#define pb push_back

#define mp make_pair
#define all(a) (a).begin(),(a).end()

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

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

ll keta(ll n){
  string s = to_string(n);
  ll num = s.size();
  return num;
}

const ll INF = 1LL << 60;

const int dh[4] = {1,0,-1,0};
const int dw[4] = {0,1,0,-1};

struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w){}
};
using Graph = vector<vector<Edge>>;
using P = pair<ll, int>;

class UnionFind{
  public:
  vi Parent;
  UnionFind(int n){
    Parent = vi(n,-1);
  }

  int root(int a){
    if(Parent[a] < 0) return a;
    else return Parent[a] = root(Parent[a]);
  }

  int size(int a){
    return -Parent[root(a)];
  }

  bool merge(int a, int b){
    a = root(a);
    b = root(b);
    if(a == b) return false;

    if(size(a) < size(b)) swap(a,b);
    Parent[a] += Parent[b];
    Parent[b] = a;

    return true;
  }
};

class Factrial{
  public:
  vl Fac;
  Factrial(int MAX){
    Fac = vl(MAX+1);
    rep(i,MAX) {
      if(i == 0) Fac[i+1] = 1;
      else Fac[i+1] = ((i+1)*Fac[i])%MOD;
    }
  }
};


int main(){
  int n,x; cin >> n >> x;
  if(x == 1 || x == 2*n-1){
    cout << "No" << endl;
    return 0;
  }

  cout << "Yes" << endl;
  if(n == 2){
    rep(i,3) cout << i+1 << endl;
    return 0;
  }

  vi ans(2*n-1,-1);
  vector<bool> used(2*n,false);
  if(x > 2){
    ans[n-2] = 1;
    used[1] = true;
    ans[n-1] = x;
    used[x] = true;
    ans[n] = x+1;
    used[x+1] = true;
    ans[n+1] = 2;
    used[2] = true;
  }
  else{
    ans[n-2] = x+2;
    used[x+2] = true;
    ans[n-1] = x;
    used[x] = true;
    ans[n] = x-1;
    used[x-1] = true;
    ans[n+1] = x+1;
    used[x+1] = true;
  }

  int num = 1;
  rep(i,2*n-1) {
    if(ans[i] != -1) continue;
    while(used[num]) num++;
    ans[i] = num;
    used[num] = true;
  }

  rep(i,2*n-1) cout << ans[i] << endl;

}

Measured memory_bytes: 2304
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
 
const int N = 12 + 10, mod = 1e9 + 7;

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

int a[N][N], dp[(1 << N)];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> a[i][j];
	dp[0] = 1;
	for (int mask = 0; mask < (1 << n) - 1; mask++) {
		int j = __builtin_popcount(mask);
		for (int i = 0; i < n; i++) {
			if(a[j][i] && !(mask & (1 << i))) {
				int up = mask | (1 << i);
				sum(dp[up], dp[mask]);
			}
		}
	}
	cout << dp[(1 << n) - 1] << "\n";
}

Measured memory_bytes: 10496