akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef set<int> si;
typedef map<string, int> msi;
typedef greater<int> gt;
typedef priority_queue<int, vector<int>, gt> minq;
typedef long long ll;
const ll INF = 1e18L + 1;

int A[100010];
int main() {
  int H, N; cin>>H>>N;
  ll sum = 0;
  rep(i,N) {
    int a; cin>>a; sum+=a;
  }
  puts(H<= sum? "Yes":
  "No");
  

  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int n,a[20];


int solve(int i,int m){
    int res;
    if(m==0)return 1;
    if(i>=n)return 0;
    res=solve(i+1,m-a[i])||solve(i+1,m);
    return res;
}

int main(){
    int q,k;

    scanf("%d",&n);

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

    scanf("%d",&q);

    for(int i=0;i<q;i++){
        scanf("%d",&k);
        if(solve(0,k))printf("yes\n");
        else printf("no\n");
    }
    return 0;
}


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

int main() {
    string s, t;
    cin >> s >> t;
    sort(s.begin(), s.end());
    sort(t.begin(),t.end(),greater<char>());
    if(s < t)cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

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

 int V[N];
 for(int i = 0; i < N; i++){
  cin >> V[i];
 }

 int C[N];
 for(int i = 0; i < N; i++){
  cin >> C[i];
 }

 int sum = 0;
 for(int i = 0; i < N; i++){
  if(V[i] > C[i]) sum += V[i] - C[i];
 }
 cout << sum << endl;

return 0;
}


Measured memory_bytes: 256
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    from itertools import accumulate
    S = accumulate([0] + A)
    from collections import Counter
    c = Counter(S)
    ans = 0
    for e, cnt in c.items():
        if cnt >= 2:
            ans += cnt*(cnt-1)//2
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 113232
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define ll long long
ll N,A;
inline void read(ll &x)
{
	ll data=0,w=1;
	char ch=0;
	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
	if(ch=='-')w=-1,ch=getchar();
	while(ch>='0'&&ch<='9')data=((ll)data<<3)+(data<<1)+(ch^'0'),ch=getchar();
	x=data*w;
}
int main()
{
	read(N);read(A);
	printf("%lld\n",N*N-A);
	return 0;
}

Measured memory_bytes: 256
using System;

namespace _175_a
{
    internal class RainySeason
    {
        private static void Main(string[] args)
        {
            var s = Console.ReadLine();

            switch (s)
            {
                case "RRR":
                    Console.WriteLine(3);
                    break;
                case "RRS":
                case "SRR":
                    Console.WriteLine(2);
                    break;
                case "SSS":
                    Console.WriteLine(0);
                    break;
                default:
                    Console.WriteLine(1);
                    break;
            }
        }
    }
}

Measured memory_bytes: 25800
#include<cstdio>
#include<iostream>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<deque>
#include<tuple>
#include<algorithm>
#include<numeric>
#include<limits>
#include<boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
using namespace std;
#define BEGIN ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define END return EXIT_SUCCESS
#define rep(I,N) for(auto I=0;I<(N);++I)
#define up(I,A,B) for(auto I=(A);I<=(B);++I)
#define dw(I,A,B) for(auto I=(A);I>=(B);--I)
#define all(C) (C).begin(),(C).end()
#define rall(C) (C).rbegin(),(C).rend()
#define ft first
#define sd second
#define mp make_pair
#define mt make_tuple
#define pf push_front
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define rs resize
typedef long long ll;
typedef unsigned long long ull;
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;}
template<class T>inline void                                      in(T &p){cin>>p;}
template<class T1,class T2>inline void                            in(T1 &p1,T2 &p2){cin>>p1>>p2;}
template<class T1,class T2,class T3>inline void                   in(T1 &p1,T2 &p2,T3 &p3){cin>>p1>>p2>>p3;}
template<class T1,class T2,class T3,class T4>inline void          in(T1 &p1,T2 &p2,T3 &p3,T4 &p4){cin>>p1>>p2>>p3>>p4;}
template<class T1,class T2,class T3,class T4,class T5>inline void in(T1 &p1,T2 &p2,T3 &p3,T4 &p4,T5 &p5){cin>>p1>>p2>>p3>>p4>>p5;}
template<class T>inline void                                      ins(T &p){for_each(all(p),in<decltype(p[0])>);}
template<class T>inline void                             out(T p){cout<<p<<endl;}
template<class T1,class T2>inline void                   out(T1 p1,T2 p2){cout<<p1<<" "<<p2<<endl;}
template<class T1,class T2,class T3>inline void          out(T1 p1,T2 p2,T3 p3){cout<<p1<<" "<<p2<<" "<<p3<<endl;}
template<class T1,class T2,class T3,class T4>inline void out(T1 p1,T2 p2,T3 p3,T4 p4){cout<<p1<<" "<<p2<<" "<<p3<<" "<<p4<<endl;}
inline                                              void out(double p){printf("%.10f\n",p);}
template<class T>inline                             void outs(T p){for_each(all(p),out<decltype(p[0])>);}
template<class T>inline void outs(vector<T> V){int n=V.size();rep(i,n)cout<<V[i]<<" \n"[i==n-1];}
inline void solve(void){
  int N,M;in(N,M);
  vector<int>A(N+1,-1);
  rep(i,M){
    int s,c;in(s,c);
    if(A[s]==-1||A[s]==c)A[s]=c;
    else{
      out(-1);
      return;
    }
  }
  if(N>1&&A[1]==0){
    out(-1);
    return;
  }
  if(N==1&&M==0){
    out(0);
    return;
  }
  up(i,1,N){
    if(i==1&&A[i]==-1)A[i]=1;
    if(i!=1&&A[i]==-1)A[i]=0;
  }
  up(i,1,N)cout<<A[i];
  cout<<endl;
}
int main(int argc,char**argv){
  BEGIN;
  solve();
  END;
}


Measured memory_bytes: 256
def main():
    n = int(input())
    a = [[int(s) for s in input().split()] for _ in range(2)]
    print(solve(n, a))

def solve(n, a):
    dp = [[0 for _ in range(n)] for _ in range(2)]

    dp[0][0] = a[0][0]
    for i in range(1, n):
        dp[0][i] = dp[0][i-1] + a[0][i]
    
    dp[1][0] = a[0][0] + a[1][0]
    for i in range(1, n):
        dp[1][i] = max(dp[0][i], dp[1][i-1]) + a[1][i]
    
    return dp[1][n-1]

main()


Measured memory_bytes: 3064
K, N = map(int, input().split())
A = sorted(list(map(int, input().split())))
difA = []
for i in range(N - 1):
    if i == 0:
        difA.append(A[i] + K - A[-1])
    else:
        difA.append(A[i + 1] - A[i])
print(K - max(difA))


Measured memory_bytes: 88652
import sys
readline = sys.stdin.readline
INF = int(1e10)
def merge(A, left, mid, right):
    L = A[left: mid] + [[0, INF]]
    R = A[mid: right] + [[0, INF]]
    i = j = 0
    for k in range(left, right):
        if L[i][1] <= R[j][1]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
def partition(A, p, r):
    x = A[r][1]
    i = p - 1
    for j in range(p, r):
        if A[j][1] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1
def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q - 1)
        quicksort(A, q + 1, r)
n = int(input())
f = lambda a: (a[0], int(a[1]))
A = [f(readline().split()) for _ in range(n)]
B = A[:]
mergeSort(A, 0, n)
quicksort(B, 0, n - 1)
print("Stable" if A == B else "Not stable")
print(*(f"{a} {b}" for a, b in B), sep="\n")



Measured memory_bytes: 23472
#include<stdio.h>

int main(void){
    int n;
    scanf("%d",&n);
    int num[n+1];
    int q;
    for(q=0;q<=n-1;q++) scanf("%d",&num[q]);
    
    int i,j,ans=0;
    for(i=0;i<=n-2;i++){
        int minj;
        minj=i+1;
        for(j=i+2;j<=n-1;j++){
            if(num[j]<num[minj]) minj=j;
        }
        if(num[i]>num[minj]){
            int a;
            a=num[i];
            num[i]=num[minj];
            num[minj]=a;
            ans++;
        }
    }
    int w;
    for(w=0;w<=n-2;w++){
        printf("%d ",num[w]);
    }
    printf("%d\n",num[n-1]);
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#define NIL -1

int N;

int main()
{
    char com[][5] = {
        {},
        {'.', ',', '!', '?', ' '},
        {'a', 'b', 'c'},
        {'d', 'e', 'f'},
        {'g', 'h', 'i'},
        {'j', 'k', 'l'},
        {'m', 'n', 'o'},
        {'p', 'q', 'r', 's'},
        {'t', 'u', 'v'},
        {'w', 'x', 'y', 'z'}
    };
    int lens[] = {0, 5, 3, 3, 3, 3, 3, 4, 3, 4};
    std::cin >> N;
    std::string msg;


    for (int t = 0; t < N; t++) {
        std::cin >> msg;
        std::string res;
        int cnt = NIL;
        char btn = '#';

        bool isPressed0 = false;

        //find first index where character is not 0
        unsigned long start = 0;
        for (unsigned long i = 0; i < msg.size(); i++) {
            if (msg[i] != '0') {
                start = i + 1;
                btn = msg[i];
                cnt = 0;
                break;
            }
        }

        for (unsigned long i = start; i < msg.size(); i++) {
            //if 0 is already pushed
            if (msg[i] == '0' && isPressed0) { continue; }

            else if (msg[i] == '0' && !isPressed0) {
                int idx = (int) btn - '0';
                res += com[idx][cnt % lens[idx]];
                isPressed0 = true;
            }

            else if (msg[i] != '0' && isPressed0) {
                cnt = 0;
                btn = msg[i];
                isPressed0 = false;
            }

            else {
                cnt++;
            }
        }

        std::cout << res << std::endl;
    }
    return 0;
}



Measured memory_bytes: 3160
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
const int INF = 100000000, mod = 1000000007;
using namespace std;

long long n, a, b, h[100000];

bool check(long long pos) {
    long long count = 0;
    for (int i = 0; i < n; i++) {
        long long tmp = h[i] - b*pos, damage = a - b;
        count += max(0LL, (tmp + damage - 1) / damage);
    }
    return count <= pos;
}

int main() {
    cin >> n >> a >> b;
    for (int i = 0; i < n; i++) cin >> h[i];
    long long left = 0, right = 1000000000;
    while (right-left>1) {//h[left]~h[right]
        long long pos = (left + right) / 2;
        if (check(pos)) right = pos;
        else left = pos;
    }
    cout << right << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
 
#define endl '\n'
#define fi first
#define se second
#define MOD(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,n) for (int i = 0; i < (n); i++)
#define forr(i,a,b) for (int i = a; i <= b; i++)
#define all(v) v.begin(), v.end()
#define pb(x) push_back(x)
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<ll, int> ii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;

const int MX = 200005;
int n, dp[MX], sig[MX][30];
string s;

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> s;
	n = s.size();

	forn (i, 30) sig[n][i] = n;
	forn (i, 30) sig[n + 1][i] = n + 1;

	for (int i = n - 1; i >= 0; i--) {
		forn (j, 30) sig[i][j] = sig[i + 1][j];
		sig[i][s[i] - 'a'] = i;
	}

	for (int i = n; i >= 0; i--) {
		dp[i] = n;
		for (int j = 'a'; j <= 'z'; j++)
			dp[i] = min(dp[i], dp[sig[i][j - 'a'] + 1] + 1);
	}

	for (int i = 0; i <= n;) {
		for (int j = 'a'; j <= 'z'; j++)
			if (dp[i] == dp[sig[i][j - 'a'] + 1] + 1) {
				cout << char(j);
				i = sig[i][j - 'a'] + 1;
				break;
			}
	}

	cout << endl;

	return 0;
}


Measured memory_bytes: 24852
#include <iostream>
#include <stdio.h>
using namespace std;

void call(int n){
  int i = 1;
 CHECK_NUM:
  int x = i;
  if ( x % 3 == 0 ){
    cout << " " << i;
    goto END_CHECK_NUM;
  }
 INCLUDE3:
  if ( x % 10 == 3 ){
    cout << " " << i;
    goto END_CHECK_NUM;
  }
  x /= 10;
  //printf("x %d ", x);
  //printf("i %d\n", i);
  if ( x != 0) goto INCLUDE3;
 END_CHECK_NUM:
  if ( ++i <= n ) goto CHECK_NUM;

  cout << endl;
}


void call0(int n){
    int i = 1;
    //printf("a\n");
    while(1){
        //printf("aa\n");
        int x = i;
        //printf("aaa\n");
        if(x % 3 == 0){
            cout << " " << i;
            if(++i > n){
                break;
            }
        }
        else{
            while(1){
                if(x % 10 == 3){
                    cout << " " << i;
                    break;
                }
                else{
                    x = x/10;
                    if (x == 0){
                        break;
                    }
                }
                //printf("included3");
            }
            if(++i > n){
                break;
            }
        }
    }
    cout << endl;
}


int main(){
    //call(30);

    //printf("\n");
    int n;
    cin >> n;
    call0(n);

    return 0;

}


Measured memory_bytes: 3096
A, B, C = map(int, input().split())

if A%2 == 0 and A == B and A == C:
    print(-1)
else:
    N = 0
    while A%2 == B%2 == C%2 == 0:
         N += 1
         A, B, C = (B + C)/2, (C + A)/2, (A + B)/2
    print(N)


Measured memory_bytes: 9184
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;


/**
 *
 * @author
 *
 *
 *
 */

public class Main {

	public static boolean isBeatiful(String string) {
        String letters = "abcdefghijklmnopqrstuvwxyz";
        char[] alphabet = letters.toCharArray();
        int[] frequency = new int[alphabet.length];

        for (int i = 0; i < string.length(); i++) {
            if (Character.isLetter(string.charAt(i))) {
                frequency[string.charAt(i) - 'a']++;
            }
        }

        boolean isBeatiful = true;
        for (int i = 0; i < frequency.length; i++) {
            if ( frequency[i] % 2 != 0) {
                isBeatiful = false;
                break;
            }
        }

        return isBeatiful;
	}

    public static void main(String[] args) throws IOException {
        MyScanner scanner = new MyScanner();
        PrintStream out = System.out;

        String string = scanner.next();

        out.println( Main.isBeatiful(string) ? "Yes" : "No" );

        scanner.reader.close();
        out.close();
    }

    // -----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader reader;

        public MyScanner() {
            this.reader = new BufferedReader(new InputStreamReader(System.in));
        }

        public void close() throws IOException {
            this.reader.close();
        }

        int nextInt() {
            return Integer.parseInt(this.next());
        }

        long nextLong() {
            return Long.parseLong(this.next());
        }

        double nextDouble() {
            return Double.parseDouble(this.next());
        }

        String next() {
            String str = "";
            try {
                str = this.reader.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        String[] nextStringArray() {
            String[] str = null;
            try {
                str = this.reader.readLine().trim().split(" ");
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        int[] nextIntArray() {
            String[] data  = nextStringArray();
            int[] a  = new int[data.length];

            for (int i = 0; i < a.length; i++) {
                a[i] = Integer.parseInt(data[i]);
            }

            return a;
        }

        Integer[] nextIntegerArray() {
            String[] data  = nextStringArray();
            Integer[] a  = new Integer[data.length];

            for (int i = 0; i < a.length; i++) {
                a[i] = Integer.parseInt(data[i]);
            }

            return a;
        }

        long[] nextLongArray() {
            String[] data  = nextStringArray();
            long[] a  = new long[data.length];

            for (int i = 0; i < a.length; i++) {
                a[i] = Long.parseLong(data[i]);
            }

            return a;
        }
    }
}



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

int main(){
    int a[3][3];
    int n;
    vector<int> b(n);
    rep(i,3){
        rep(j,3){
            cin>>a[i][j];
        }
    }
    cin >> n;
    rep(i,n) cin >> b[i];
    rep(i,n){
        rep(j,3){
            rep(k,3){
                if(a[j][k]==b[i])a[j][k]= -1;
            }
        }
    }
    if((a[0][0]==-1&&a[1][1]==-1&&a[2][2]==-1)||(a[0][2]==-1&&a[1][1]==-1&&a[2][0]==-1)||
    (a[0][0]==-1&&a[1][0]==-1&&a[2][0]==-1)||(a[0][1]==-1&&a[1][1]==-1&&a[2][1]==-1)||
    (a[0][2]==-1&&a[1][2]==-1&&a[2][2]==-1)||(a[0][0]==-1&&a[0][1]==-1&&a[0][2]==-1)||
    (a[1][0]==-1&&a[1][1]==-1&&a[1][2]==-1)||(a[2][0]==-1&&a[2][1]==-1&&a[2][2]==-1)){
        cout <<"Yes" <<endl;
        return 0;
    }
    else cout << "No"<<endl;

}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,d,x; cin>>n>>d>>x;
    vector<int> a(n);
    for(int i=0; i<n; ++i){
        cin>>a[i];
    }
    int f = x;
    for(int i=0; i<n; ++i) {
        int m = 1;
        int c = 0;
        while(m <= d){
            c += 1;
            m += a[i];
        }
        f += c;
    }
    cout<<f<<endl;

    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  int n;
  cin >> n;
  if(n == 1) {
    cout << "Hello World" << endl;
  } else {
    int a, b;
    cin >> a >> b;
    cout << a + b << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    long long n;
    cin >> n;
    long long a[n], b[n], c[n], dpa[n + 1], dpb[n + 1], dpc[n + 1];
    dpa[0] = 0;
    dpb[0] = 0;
    dpc[0] = 0;
    for (long long i = 0; i < n; i++)
    {
        cin >> a[i] >> b[i] >> c[i];
        dpa[i + 1] = a[i] + max(dpb[i], dpc[i]);
        dpb[i + 1] = b[i] + max(dpa[i], dpc[i]);
        dpc[i + 1] = c[i] + max(dpa[i], dpb[i]);
    }
    cout << max(max(dpa[n], dpb[n]), dpc[n]);
}

Measured memory_bytes: 8252
#include <bits/stdc++.h>
#define rep(i, N) for (int i = 0; i < N; i++)
#define vec vector<int>
using namespace std;
int main()
{
    int N, K, X, Y, sum1;

    cin >> N >> K >> X >> Y;
    if (N > K)
    {
        for (int i = 0; i < K; i++)
        {
            sum1 += X;
        }
        for (int i = K + 1; i <= N; i++)
        {
            sum1 += Y;
        }
    }
    else
    {
        sum1 = X * N;
    }
    cout << sum1 << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		int a=sc.nextInt();
		int b=sc.nextInt();
		int c=sc.nextInt();
		
		if(a==b+c || b==a+c || c==a+b)System.out.println("Yes");
		else System.out.println("No");
		
	}

}


Measured memory_bytes: 9684
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
 
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; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()

const int mod=1e9+7;

int main(){
  int n,m;cin>>n>>m;
  VI G[n];
  rep(i,m){
    int p,q;cin>>p>>q;
    G[--p].push_back(--q);
  }
  if(m==0){
    cout<<-1<<endl;
    exit(0);
  }
  int s,t;cin>>s>>t;
  --s;--t;
  queue<int> Q;
  Q.push(s);
  int reached[3][m];
  rep(i,3) rep(j,m) reached[i][j]=mod;
  reached[0][s]=0;
  int ctr=1;
  while(!Q.empty()){
    int qtop=Q.front();
    Q.pop();
    for(auto v:G[qtop]){
      rep(i,3){
        if(reached[i][qtop]!=mod){
          if(chmin(reached[(i+1)%3][v],reached[i][qtop]+1))Q.push(v);
        }
      }
    }
    ctr++;
  }
  if(reached[0][t]!=mod)cout<<reached[0][t]/3<<endl;
  else cout<<-1<<endl;
}




Measured memory_bytes: 6912
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef int64_t Int;
using namespace std;
 
int main(){
    int N, A, B, C;
    vector<int> L(8);
    cin >> N >> A >> B >> C;
    rep(i, N) cin >> L[i];

    int ans = 1e8;
    rep(bits, 1<<(2*N)){
        int cur = bits;
        int a = 0, b = 0, c = 0;
        int cnta=0, cntb=0, cntc=0;
        rep(i, N){
            int state = cur & 3; cur >>= 2;
            if(state == 1) {a += L[i]; cnta++;}
            if(state == 2) {b += L[i]; cntb++;}
            if(state == 3) {c += L[i]; cntc++;}
        }
        if(a == 0 || b == 0 || c == 0) continue;

        int tmp = abs(A-a)+abs(B-b)+abs(C-c);
        tmp += 10*(cnta+cntb+cntc-3);
        ans = min(ans, tmp);
    }

    cout << ans << endl;
}

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

int main(){
	int data[5];
	for(int i=0;i<5;i++)cin>>data[i];
	
	sort(data,data+5,greater<int>());
	for(int i=0;i<4;i++)cout<<data[i]<<" ";
	cout<<data[4]<<endl;
}

Measured memory_bytes: 1176
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cmath>
#include <complex>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cassert>
#include <iomanip>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define Repr(e, b, i) for(int i = e; i >= b; i--)
#define rep(n, i) Rep(0, n-1, i)
#define repr(n, i) Repr(n-1, 0, i)
#define all(v) (v).begin(), (v).end()
#define pb(v) push_back(v)
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define bitcnt(x) __builtin_popcount(x)
#define fst first
#define snd second
#define Pqaz(T) priority_queue<T,vector<T>,greater<T>>
#define Pqza(T) priority_queue<T>
#define put(x) cout << x;
#define putsp(x) cout << x << ' ';
#define putbd cout << "---------------------------------------------" << endl;
#define putln(x) cout << x << endl;
#define debug(x) cerr << #x << "=" << x << endl;
#define ENJYU std::ios::sync_with_stdio(false);std::cin.tie(0);

typedef long long ll;
typedef pair<ll, ll> llP;
typedef pair<int, int> intP;
typedef complex<double> comp;
typedef vector <int> vec;
typedef vector <ll> vecll;
typedef vector <double> vecd;
typedef vector <vec> mat;
typedef vector <vecll> matll;
typedef vector <vecd> matd;

//vector の中身を出力
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

const int MAX = 200020;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const ll INFL = 1e18;
const int MOD = 1000000007;

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

//********************************template END****************************************//

void solve(void){

	int N, M;
	cin >> N >> M;
	vector <intP> ps(M);
	rep(M, i)
	{
		cin >> ps[i].fst >> ps[i].snd;
	}

	sort(all(ps));

	int l = ps[0].fst, r = ps[0].snd, ans = 0;

	rep(M, i)
	{
		if (r <= ps[i].fst)
		{
			ans++;
			l = ps[i].fst;
			r = ps[i].snd;
			continue;
		}
		l = ps[i].fst;
		r = min(r, ps[i].snd);
	}

	if (l < r)
	{
		ans++;
	}

	cout << ans << endl;

}

int main(void){
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>

using namespace std;

#define ll long long
#define pii pair<int,int>
#define N 600600
#define dracarys ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);

const ll mod = 998244353;

int n;

char d[N];
int x[N], y[N];

vector<pii> Lx[N], Ly[N], Ld1[N], Ld2[N];

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> x[i] >> y[i] >> d[i];

    int z = 200000;
    for (int i = 1; i <= n; ++i) {
        Lx[x[i]].emplace_back(y[i], i);
        Ly[y[i]].emplace_back(x[i], i);
        Ld1[x[i] - y[i] + z].emplace_back(x[i], i);
        Ld2[x[i] + y[i] + z].emplace_back(x[i], i);
    }

    for (int i = 0; i <= z; ++i) {
        sort(Lx[i].begin(), Lx[i].end());
        sort(Ly[i].begin(), Ly[i].end());
    }

    for (int i = 0; i <= 3 * z; ++i) {
        sort(Ld1[i].begin(), Ld1[i].end());
        sort(Ld2[i].begin(), Ld2[i].end());
    }

    int ans = (int)1e9;

    for (int i = 0; i <= z; ++i) {
        int last = -1;
        for (int j = 0; j < Lx[i].size(); ++j) {
            int id = Lx[i][j].second;
            if (last != -1 && d[id] == 'D')
                ans = min(ans, Lx[i][j].first - Lx[i][last].first);
            if (d[id] == 'U')
                last = j;
        }
    }

    for (int i = 0; i <= z; ++i) {
        int last = -1;
        for (int j = 0; j < Ly[i].size(); ++j) {
            int id = Ly[i][j].second;
            if (last != -1 && d[id] == 'L')
                ans = min(ans, Ly[i][j].first - Ly[i][last].first);
            if (d[id] == 'R')
                last = j;
        }
    }


    for (int i = 0; i <= 3 * z; ++i) {
        int lastu = -1, lastr = -1;
        for (int j = 0; j < Ld1[i].size(); ++j) {
            int id = Ld1[i][j].second;
            if (lastu != -1 && d[id] == 'L')
                ans = min(ans, 2 * (Ld1[i][j].first - Ld1[i][lastu].first));
            if (lastr != -1 && d[id] == 'D')
                ans = min(ans, 2 * (Ld1[i][j].first - Ld1[i][lastr].first));
            if (d[id] == 'U') lastu = j;
            if (d[id] == 'R') lastr = j;
        }
    }


    for (int i = 0; i <= 3 * z; ++i) {
        int lastd = -1, lastr = -1;
        for (int j = 0; j < Ld2[i].size(); ++j) {
            int id = Ld2[i][j].second;

            if (lastd != -1 && d[id] == 'L')
                ans = min(ans, 2 * (Ld2[i][j].first - Ld2[i][lastd].first));
            if (lastr != -1 && d[id] == 'U')
                ans = min(ans, 2 * (Ld2[i][j].first - Ld2[i][lastr].first));

            if (d[id] == 'D') lastd = j;
            if (d[id] == 'R') lastr = j;
        }
    }

    if (ans == (int)1e9) cout << "SAFE\n";
    else cout << ans * 5 << "\n";
}


int main() {
//    freopen("sample.in", "r", stdin);
    dracarys
    int t = 1;
//    cin >> t;
    for (int i = 1; i <= t; ++i) {
//        cout << "Case #" << i << ": ";
        solve();
    }
    return 0;
}


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

int main(){
  int n, y;
  cin >> n >> y;
  
  bool ans = true;
  
  for(int i = 0; i <= n; i++){
  for(int j = 0; i+j <= n; j++){
  
    if(10000*i+5000*j+1000*(n-i-j) == y){
    	ans = false;
    	cout << i << ' ' << j << ' ' << n-i-j << endl;
      	break;
    }
    
  }
    if(!ans) break;
  }
  
  if(ans) cout << -1 << ' ' << -1 << ' ' << -1 << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

int main()
{
	int a, b, c;
	char x, y, z;
	
	cin >> a >> x >> b >> y >> c >> z;
	
	if(a>2019)
	{
		cout << "TBD";
	}
	else
	{
		if(b>4)
		{
			cout << "TBD";
		}
		else
		{
			if(c>30)
				cout << "TBD";
			else
				cout << "Heisei";
		}
	}
	return 0;
		
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define inf 20021225
#define ll long long
#define mdn 1000000007
using namespace std;

int f[2100][2100];
int inv[2100*2100],fac[2100*2100];
int n,k;

int ksm(int bs,int mi)
{
	int ans=1;
	while(mi)
	{
		if(mi&1)	ans=(ll)ans*bs%mdn;
		bs=(ll)bs*bs%mdn; mi>>=1;
	}
	return ans;
}

int C(int x,int y)
{
	if(x<y)	return 0;
	return (ll)fac[x] * inv[y] %mdn * inv[x-y] %mdn;
}

int main()
{
	scanf("%d%d",&n,&k);
	if(k==1||n==1){printf("1\n");return 0;}
	inv[0]=fac[0]=1; int tot=n*k;
	for(int i=1;i<=tot;i++)	fac[i]=(ll)fac[i-1]*i%mdn;
	inv[tot] = ksm(fac[tot],mdn-2);
	for(int i=tot-1;i;i--)	inv[i]=(ll)inv[i+1]*(i+1)%mdn;
	f[0][0]=1;// printf("%d\n",inv[tot]);
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=i;j++)
		{
			f[i][j] += f[i-1][j];
			if(j) f[i][j] += (ll)f[i][j-1] * C(tot-i-(k-1)*(j-1)-1,k-2) %mdn;
			f[i][j]%=mdn;
			//printf("%d %d %d\n",i,j,f[i][j]);
		}
	}
	printf("%d\n",(ll)f[n][n]*fac[n]%mdn);
	return 0;
}

Measured memory_bytes: 51328
s = input()


def check2(s: str):
    return s.count('C') == 1


def check3(s: str):
    for c in s:
        if c == 'A' or c == 'C':
            continue
        if str(c).isupper():
            return False
    return True

def check(s):
    if s[0] != 'A':
        return False
    if check2(s[2:-1]) == False:
        return False
    return check3(s)

print("AC" if check(s) else "WA")

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <assert.h>
#include <numeric>
#include <iomanip>

using ll = long long;
using P = std::pair<ll, ll>;

#define rep(i, a, b) for (ll(i) = (a); i < (b); i++)
#define all(i) i.begin(),i.end()
#define debug(i) std::cout << i << "\n"



const int INF = 100000000;
const ll MOD = 1000000007;

ll pow_mod(ll x, ll y, ll mod)
{
	if (y == 0)
		return 1;
    if(y%2){
        return (x*pow_mod(x,y-1,mod))%mod;
    }else{
        return pow_mod(x*x,y/2,mod);
    }
}

int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	//問題文中の添え字が0-indexか1-indexか確認!
    int r;
    std::cin >> r;
    std::cout << 3 * r * r;
    return 0;
}

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

typedef long long ll;
#define ar array
#define vi vector<int>
#define vvi vector<vector<int>>
#define vll vector<long long>
#define all(x) (x).begin(), (x).end()
#define en '\n'
#define FILL(x, v) memset(x, v, sizeof(x))
#define pb push_back
#define fast                     \
	ios::sync_with_stdio(false); \
	cin.tie(NULL);               \
	cout.tie(NULL);
#define F_OR(i, a, b, s) for (int i = (a); ((s) > 0 ? i < (b) : i > (b)); i += (s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...)       \
	F_ORC(__VA_ARGS__) \
	(__VA_ARGS__)

#define E_ACH2(x, a) for (auto &x : a)
#define E_ACH3(x, y, a) for (auto &[x, y] : a)
#define E_ACH4(x, y, z, a) for (auto &[x, y, z] : a)
#define E_ACHC(...) GET5(__VA_ARGS__, E_ACH4, E_ACH3, E_ACH2)
#define EACH(...)       \
	E_ACHC(__VA_ARGS__) \
	(__VA_ARGS__)

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 main()
{
	fast;
	int n;
	cin >> n;
	ll ans[n + 1] = {};
	for (int a = 1; a <=101; a++)
	{
		for (int b = 1; b <= 101; b++)
		{
			for (int c = 1; c <= 101; c++)
			{
				ll cur = a * a + b * b + c * c + a * b + b * c + a * c;
				if (cur <= n)
					ans[cur]++;
			}
		}
	}
	FOR(n)
	cout << ans[i + 1] << en;
}

Measured memory_bytes: 3724
#include<stdio.h>
#define N 10000

int main(){

  int i,j,n,k,count=0;
  int S[N],T[N];

  scanf("%d",&n);

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

  for(i=0;i<k;i++){
    scanf("%d",&T[i]);
  }

  for(i=0;i<k;i++){
    for(j=0;j<n;j++){
      if(S[j]==T[i]){
	count++;
	break;
      }
    }
  }
  printf("%d\n",count);
  return 0;
}

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

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


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<stdlib.h>

int main(){
  int n,i,p[9],q[9],tmp=1,kai[8];
  char s[51];
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&p[i]);
  }
  for(i=0;i<n;i++){
    scanf("%d",&q[i]);
  }

  for(i=1;i<=7;i++){
    tmp*=i;
    switch (i)
    {
    case 1:
      kai[1]=tmp;
      break;
    case 2:
      kai[2]=tmp;
    case 3:
      kai[3]=tmp;
      break;
    case 4:
      kai[4]=tmp;
      break;
    case 5:
      kai[5]=tmp;
      break;
    case 6:
      kai[6]=tmp;
      break;
    case 7:
      kai[7]=tmp;
      break;
  }
  }

  int sump=0,sumq=0;

  for(i=0;i<n;i++){
    int pp=p[i];
    for(int j=0;j<i;j++){
      if(p[i]>p[j]) pp--;
    }
    sump+=(pp-1)*kai[n-i-1];
  }

  for(i=0;i<n;i++){
    int qq=q[i];
    for(int j=0;j<i;j++){
      if(q[i]>q[j]) qq--;
    }
    sumq+=(qq-1)*kai[n-i-1];
  }
  printf("%d",abs(sump-sumq));
  return 0;
}

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

int main(){
  string S;
  cin >> S;
  int len_S = S.length();
  
  for (int i = 1; i <= len_S; i++) {
    if (i % 2 == 1) {
      if (S[i-1] == 'L') {
        cout << "No";
        return 0;
      }
    }
    else {
      if (S[i-1] == 'R') {
        cout << "No";
        return 0;
      }
    }
  }
  
  cout << "Yes";
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int main(int argc, char const *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(0);
    long long n;
    cin>>n;
    n--;
    cout<<(n*(n+1)/2)<<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
	static int check(int i,int j,int h,int w) {
		if(i*i+j*j == h*h+w*w) {
			return i-h;
		}else {
			return (i*i+j*j) - (h*h+w*w);
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int h = sc.nextInt();
			int w = sc.nextInt();
			if(h==0 && w==0) break;
			int H = 150;
			int W = 150;
			for(int i=1;i<=150;i++) {
				for(int j=i+1;j<=150;j++) {
					if(check(i,j,h,w)>0 && check(i,j,H,W)<0) {
						H = i;
						W = j;
					}
				}
			}
			System.out.println(H+" "+W);
		}
	}
}



Measured memory_bytes: 27680
#UnionFind
def root(nodes,x):
    if nodes[x] < 0:
        return x
    else:
        nodes[x] = root(nodes,nodes[x])
        return nodes[x]

def unite(nodes,x,y):
    root_x, root_y = root(nodes,x) , root(nodes,y)
    if root_x != root_y:
        nodes[root_x] = root_y

def is_same(nodes,x,y):
    return root(nodes,x) == root(nodes,y)



N,M = list(map(int,input().split()))
p = list(map(int,input().split()))
x_y = [list(map(int,input().split())) for i in range(M)]
nodes = [-1]*(N+1)
cnt = 0

for x,y in x_y:
    unite(nodes,x,y)


for i in range(N):
    if is_same(nodes,i+1,p[i]):cnt += 1

print(cnt)

Measured memory_bytes: 32092
import java.util.*;
 
 
public class Main {
    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
      int N = sc.nextInt();
      int M = sc.nextInt();
      int multi = (N*M)%2;
      if(multi == 1){
        System.out.println("Odd");
      }else{
        System.out.println("Even");
      }
         }
}

Measured memory_bytes: 21588
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
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;
vector<ll> h(100010), dp(100010);

int main(){
  int N;
  cin >> N;
  for(int i = 0; i < N; i++){
    cin >> h.at(i);
  }

  //初期化
  for(int i = 0; i < 100010; i++){
    dp.at(i) = INF;
  }

  //初期条件
  dp.at(0) = 0;

  //ループ
  for(int i = 0; i < N-1; i++){
    chmin(dp.at(i+1), dp.at(i) + abs(h.at(i+1) - h.at(i)));
    chmin(dp.at(i+2), dp.at(i) + abs(h.at(i+2) - h.at(i)));
  }

  cout << dp.at(N-1) << endl;
}

Measured memory_bytes: 1792
n, k = gets.chomp.split(' ').map(&:to_i)
h = readlines.map(&:chomp).map(&:to_i).sort

min = 1000000000
h.each_with_index do |hh, i|
  if i == n - k + 1 
    break
  else
    min = (min > (h[i + k - 1] - h[i])) ? h[i + k - 1] - h[i] : min
  end
end

p min


Measured memory_bytes: 14840
#include <bits/stdc++.h>
using namespace std;
//#define LOCAL
#define fastIO ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define forn(i,a,b) for(int i=a;i<b;i++)
#define ft first
#define sd second
#define sz size()
#define pb push_back
#define pob pop_back()
#define pf push_front
#define pof pop_front()
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<double,double> pdd;
typedef pair<long long,long long> pll;
//cout << fixed << setprecision(12) <<x<<endl;
const int MAX=30;
int a[MAX];
int b[MAX];
int c[MAX];
int main(){
fastIO;
#ifdef LOCAL
     freopen("int.txt", "r", stdin);
#endif

int n;
cin>>n;
forn(i,0,n) cin>>a[i];
int sum=0;
forn(i,0,n){
    cin>>b[i];
    sum+=b[i];
}
forn(i,0,n) cin>>c[i];
forn(i,0,n-1){
   // if(i==0) continue;
    if(a[i]+1==a[i+1]){
        sum+=c[a[i]-1];
    }
}
cout<<sum<<endl;
}



Measured memory_bytes: 3628
# Let N be max{r_i} = 10^5.
# time complexity: O(NlglgN + Q)
# space complexity: O(N)

import sys
fin = sys.stdin.readline


def sieve(n):
    is_prime = [True] * (n + 1)
    prime_numbers = []
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        if is_prime[i]:
            prime_numbers.append(i)
            for j in range(2 * i, n + 1, i):
                is_prime[j] = False
    return is_prime


Q = int(fin())
N = 10**5
queries = [[int(elem) for elem in fin().split()] for _ in range(Q)]
is_prime = sieve(N)
num_similar_prefix = [0] * (N + 1)
num_similar = 0
for i in range(1, N + 1):
    if is_prime[i] and is_prime[(i + 1) // 2]:
        num_similar += 1
    num_similar_prefix[i] = num_similar

for l, r in queries:
    if l == 0:
        num_similar = num_similar_prefix[r]
    else:
        num_similar = num_similar_prefix[r] - num_similar_prefix[l - 1]
    print(num_similar)


Measured memory_bytes: 23580
n=int(input())
*a,=map(int,input().split())
*b,=map(int,input().split())

x,y=0,0
for i,j in zip(a,b):
  if i>j:x+=i-j
  else:y+=(j-i)//2
print('Yes' if y >= x else 'No')

Measured memory_bytes: 4596
void main(){
	int n = _scan();
	(n/2 +n%2).writeln();
}

import std.stdio, std.conv, std.algorithm, std.numeric, std.string, std.math;

// 1要素のみの入力
T _scan(T= int)(){
	return to!(T)( readln().chomp() );
}

// 1行に同一型の複数入力
T[] _scanln(T = int)(){
	T[] ln;
	foreach(string elm; readln().chomp().split()){
		ln ~= elm.to!T();
	}
	return ln;
}


Measured memory_bytes: 2628
using System;
using System.Text;

namespace ALDS1_4_C {
    class Problem {
        bool[] _memo = new bool[244140625];

        public void Run() {
            int n = int.Parse(Console.ReadLine());
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                string[] input = Console.ReadLine().Split(' ');
                if (input[0] == "insert")
                    Insert(input[1]);
                else
                    sb.AppendLine(Find(input[1]) ? "yes" : "no");
            }
            Console.Write(sb);
        }

        private void Insert(string source) {
            _memo[Convert(source)] = true;
        }
        private bool Find(string source) {
            return _memo[Convert(source)];
        }

        private int Convert(string source) {
            int ret = 0;
            for (int i = 0; i < source.Length; i++) {
                ret = ret * 5 + CharToInt(source[i]);
            }
            return ret;
        }

        private int CharToInt(char ch) {
            switch (ch) {
                case 'A':
                    return 1;
                case 'C':
                    return 2;
                case 'G':
                    return 3;
                case 'T':
                    return 4;
            }
            return -1;
        }
    }

    class Program {
        static void Main(string[] args) {
            Problem p = new Problem();
            p.Run();
        }
    }
}

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

#define NREP() for(ll i = 0; i < n; i++)
#define MREP() for(ll j = 0; j < m; j++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define ALL(x) (x).begin(), (x).end()
#define MSG(x) cout << x << endl;
#define IPT(t, x) t ipt; cin >> ipt; x.push_back(ipt);
#define YN(x) x ? cout << "YES" << endl : cout << "NO" << endl;
#define Yn(x) x ? cout << "Yes" << endl : cout << "No" << endl;
#define yn(x) x ? cout << "yes" << endl : cout << "no" << endl;

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;

const static ll MOD = 1e9 + 7;
ll n, cnt, ans, tmp, sum, a, b, c, d, k, m, h, w, q, x, y;
string s, t;

int main() {
    cin >> a >> b >> c >> k;
    ll mx = max(a, max(b, c));
    if (a == mx) {
        REP(i, k) {
            mx *= 2;
        }
        MSG(mx + b + c)
    } else if (b == mx) {
        REP(i, k) {
            mx *= 2;
        }
        MSG(mx + a + c)
    } else {
        REP(i, k) {
            mx *= 2;
        }
        MSG(mx + a + b)
    }
}


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


int main(){
  int n,m,X,Y;
  cin >> n >> m >> X >> Y;
  vector<int> x(n),y(m);
  for(int i=0;i<n;++i) cin >> x[i];
  for(int i=0;i<m;++i) cin >> y[i];

  bool ok=true;
  if(Y-X<1) ok=false;
  if(!ok){
    cout << "War" << endl;
    return 0;
  }
  sort(x.begin(),x.end());
  sort(y.begin(),y.end());
  ok=false;
  for(int z=Y;z>X;--z){
    if(x[n-1]<z && y[0]>=z){
      ok=true;
      break;
    }
  }
  if(ok) cout << "No War" << endl;
  else cout << "War" << endl;
  return 0;
}


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

signed main(){
  string s; cin >> s;
  int n = s.size();
  for(int i = 0; i < n - 1; i++){
    if(s[i] == s[i + 1]){
      cout << i + 1 << " " << i + 2 << endl;
      return 0;
    }
    if(i < n - 2 && s[i] == s[i + 2]){
      cout << i + 1 << " " << i + 3 << endl;
      return 0;
    }
  }
  cout << -1 << " " << -1 << endl;
}

Measured memory_bytes: 512
N, K = map(int, input().split())
# 出た目をaとすると、log_2([N/a])回振る必要がある.
# 求めるのは(1/N)*(1/2)**log_2([N/a])

ans = 0
for i in range(1, N+1):
    tmp = 1 / N
    now = i
    while now < K:
        now *= 2
        tmp /= 2
    ans += tmp
print(ans)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)n; i++)
#define REPvec(itr, mp) for (auto itr = mp.begin(); itr != mp.end(); itr++)
#define all(x) x.begin(), x.end()
#define MOD 1000000007  // 1e9+7
using namespace std;
typedef long long ll;
typedef vector<bool> vecbool;
typedef vector<int> vecint;
typedef vector<ll> vecll;
typedef vector<string> vecstr;
typedef vector<vecint> vec2int;
typedef vector<vecbool> vec2bool;
int dx[4]{-1, +1, 0, 0};
int dy[4]{0, 0, -1, +1};

void init() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}
int main() {
  init();
  int n;
  cin >> n;
  vec2int g(n, vecint(n, 0));
  REP(i, n) REP(j, n) cin >> g[i][j];
  vector<vecll> dp(n + 1, vecll((1 << n), 0));
  dp[0][0] = 1;
  vector<set<int> > bv(n + 1);
  for (int bit = 0; bit < (1 << n); bit++) {
    // cout << bit << endl;
    bv[__builtin_popcount(bit)].insert(bit);
  }
  // REP(i, n + 1) {
  //   cout << "i :" << i << " ";
  //   for (auto itr = bv[i].begin(); itr != bv[i].end(); itr++) {
  //     cout << *itr << " ";
  //   }
  //   cout << endl;
  // }
  // return 0;
  REP(i, n) {
    // for (int bit = 0; bit < (1 << n); bit++) {
    for (auto& bit : bv[i]) {
      // cout << k << endl;
      // int bit = e;
      // cout << bit << endl;
      for (int j = 0; j < n; j++) {
        if (g[i][j] == 0) continue;
        if (!((bit >> j) & 1)) {
          dp[i + 1][(bit | 1 << j)] += dp[i][bit];
          if (dp[i + 1][(bit | 1 << j)] > MOD) dp[i + 1][(bit | 1 << j)] %= MOD;
        }
      }
    }
  }
  cout << dp[n][(1 << n) - 1] << endl;
}


Measured memory_bytes: 461180
#include<bits/stdc++.h>
typedef long long ll;
unsigned popcount (unsigned u)
{
    u = (u & 0x55555555) + ((u >> 1) & 0x55555555);
    u = (u & 0x33333333) + ((u >> 2) & 0x33333333);
    u = (u & 0x0F0F0F0F) + ((u >> 4) & 0x0F0F0F0F);
    u = (u & 0x00FF00FF) + ((u >> 8) & 0x00FF00FF);
    u = (u & 0x0000FFFF) + ((u >> 16) & 0x0000FFFF);
    return u;
}

int n,m;
struct Edge{
	int nxt,to;
}e[110];
int color[110];
int head[55],cnt=2;
int uu[22],vv[22];
void inline add(int u,int v)
{
	e[cnt]={head[u],v};
	head[u]=cnt++;
}
bool dfs(int u,int fa,int aid)
{
	if(u==aid) return true;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa) continue;
		if(dfs(v,u,aid))
		{
			color[i]=color[i^1]=1;
			return true;
		}
	}
	return false;
}
int sum()//统计color数组中有多少个1
{
	int ans=0;
	for(int i=2;i<cnt;i+=2) if(color[i]) ans++;
	return ans;
}
int main()
{
	// freopen("test.in","r",stdin);
	scanf("%d",&n);
	for(int i=1,u,v;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	scanf("%d",&m);
	for(int i=0;i<m;i++)
		scanf("%d%d",&uu[i],&vv[i]);
	long long ans=(1LL<<(n-1));//违反0条规则
	for(unsigned mask=1;mask<=(1U<<m)-1;mask++)
	{
		memset(color,0,sizeof(int)*cnt+2);
		for(int i=0;i<m;i++)
			if((1<<i)&mask)
				dfs(uu[i],0,vv[i]);
		int ss=n-1-sum();
		if(popcount(mask)&1) ans-=1LL<<ss;
		else ans+=1LL<<ss;
	}
	printf("%lld\n",ans);
	return 0;
}


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

int main(){
    int H, N;
    cin >> H >>N;
    vector<pair<int, int>> a(N);
    int dp[N][H+1];
    
    for(int i=0; i<N; i++){
	cin >> a[i].first >> a[i].second;
    }
    sort(a.begin(), a.end());

    for(int i=0; i<H+1; i++){
	dp[0][i]=(i%a[0].first==0? i/a[0].first*a[0].second: (i/a[0].first+1)*a[0].second);
	// cout << dp[0][i] << " ";
    }

    for(int i=0; i<N; i++){
	dp[i][0]=0;
    }
    
    for(int i=1; i<N; i++){
	for(int j=0; j<H+1; j++){
	    int right=j-a[i].first;
	    if(right<0)
		right=0;
	    
	    dp[i][j]=min(min(dp[i-1][right]+a[i].second, dp[i-1][j]), dp[i][right]+a[i].second);
	}
    }
    cout << dp[N-1][H] << endl;

}

 


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

using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<string>x;
    string h;
    cin>>h;
    x.push_back(h);
    bool ans = false;
    for(int i=1;i<n;i++){
        string j;
        cin>>j;
        string u = x[i-1];
        x.push_back(j);
        if(count(x.begin(),x.end(),j)>1||j[0]!=u[u.length()-1]){
           ans=true;
        }
    }
    if(ans){
        cout<<"No"<<endl;
    }else{
        cout<<"Yes"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256