akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;

namespace paiza
{
    class Program
    {
        static void Main(string[] args)
        {
            //var NK = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
            var S = Console.ReadLine();

            bool isYYMM;
            bool isMMYY;

            if (int.Parse(S[0].ToString()) > 2 || (int.Parse(S[0].ToString()) == 1 && int.Parse(S[1].ToString()) > 2) || (int.Parse(S[0].ToString()) == 0 && int.Parse(S[1].ToString()) == 0))
            {
                isMMYY = false;
            }
            else
            {
                isMMYY = true;
            }

            if (int.Parse(S[2].ToString()) > 2 || (int.Parse(S[2].ToString()) == 1 && int.Parse(S[3].ToString()) > 2) || (int.Parse(S[2].ToString()) == 0 && int.Parse(S[3].ToString()) == 0))
            {
                isYYMM = false;
            }
            else
            {
                isYYMM = true;
            }

            var output = "";
            if (isMMYY && !isYYMM)
            {
                output = "MMYY";
            }
            else if (!isMMYY && isYYMM)
            {
                output = "YYMM";
            }
            else if (isMMYY && isYYMM)
            {
                output = "AMBIGUOUS";
            }
            else if (!isMMYY && !isYYMM)
            {
                output = "NA";
            }
            Console.WriteLine(output);
            ////foreach (var (c, i) in S.Select((x, i) => (x, i)))
            //for (var i = 0; i < NK[0]; i++)
            //{
            //    Console.Write(i + 1 == NK[1] ? S[i].ToString().ToLower() : S[i].ToString());
            //}
            //Console.WriteLine();
            //    var xai = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
            //    var N = int.Parse(Console.ReadLine());

            //    var p = new int[N];
            //    foreach (var i in Enumerable.Range(0, N))
            //    {
            //        p[i] = int.Parse(Console.ReadLine());
            //    }

            //    var reverses = new Dictionary<int, int>();

            //    for (var i = 0; i < 6; i++)
            //    {
            //        if (i % 2 == 0)
            //        {
            //            reverses.Add(xai[i], xai[i + 1]);
            //        }
            //        else
            //        {
            //            reverses.Add(xai[i], xai[i - 1]);
            //        }
            //    }

            //    var point = 0;
            //    var number = p[0];

            //    for (var i = 0; i < N - 1; i++)
            //    {
            //        if (reverses[number] == p[i + 1])
            //        {
            //            point += 2;
            //        }
            //        else if (number == p[i + 1])
            //        {

            //        }
            //        else
            //        {
            //            point += 1;
            //        }
            //        number = p[i + 1];
            //    }

            //    Console.WriteLine(point);
            //}
        }
    }
}

Measured memory_bytes: 11092
#include<iostream>
#include<sstream>
#include<vector>
#include<algorithm>
#include<string>
#include<stdexcept>
#include<stdio.h>
#include<queue>
#include<math.h>
using namespace std;
 int main(){
   int n,t,a; double mi=10e5;
   cin >>n>>t>>a;
   int h[n];
   
   for(int i=1;i<=n;i++){
     cin >> h[i];
     mi=min(mi,fabs(t-h[i]*0.006-a));
   }
   for(int i=1;i<=n;i++){
     if(mi==fabs(t-h[i]*0.006-a))
       cout << i <<endl;
   }
 }

Measured memory_bytes: 256
//gauravsinghh
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long int
#define ld long double
#define db double
#define pii pair<int,int>
#define pll pair<long long,long long>
#define sii set<int>
#define sll set<long long>
#define vii vector<int> 
#define vll vector<long long>
#define mii map<int,int>
#define mll map<long long, long long>
#define lob lower_bound
#define upb upper_bound
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define pf push_front
#define ins insert
#define mp make_pair
#define w(t) cin >> t;while(t--)
#define on cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define os cout<<" "
#define bitcount __builtin_popcount
#define gcd __gcd
#define endl "\n"
#define present(s,x) (s.find(x) != s.end()) 
#define cpresent(s,x) (find(all(s),x) != s.end()) 
#define ford(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++) 
#define fors(container, it, a, b) for(__typeof(container.begin()) it = a; it != b; it++) 
#define MOD 1000000007
#define EPSILON 1e-9
#define PI 3.14159265358979323846
#define inf 999999999999999999
#define siz 100005
#define fbo find_by_order
#define ook order_of_key
#define sz(s) (int)s.size()
#define mem(n,m) memset(n,m,sizeof(n))
#define rep(i,n) for(ll i = 0; i < n; i++)
#define ren(i,n) for(ll i = n-1; i >= 0; i--)
#define all(x) x.begin(),x.end()
#define fo(i, a, b) for(int i = a; i <= b; i++)
#define ffo(i, a, b) for(int i = a; i >= b; i--)
#define MAX 100005
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

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

void io_set() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}

bool comp(const pair < ll, ll >&a, const pair < ll, ll >&b){
    return ((a.ss < b.ss) || (a.ss == b.ss && a.ff < b.ff));
}

signed main(){ 
    IOS
    //io_set();
    string s;
    cin >> s;
    ll y = (s[0] - '0')*10 + (s[1] - '0');
    ll z = (s[2] - '0')*10 + (s[3] - '0');
    if(1 <= z && z <= 12 && 1 <= y && y <= 12){
        cout << "AMBIGUOUS\n";
    }
    else if(1 <= y && y <= 12){
        cout << "MMYY\n";
    }
    else if(1 <= z && z <= 12){
        cout << "YYMM\n";
    }
    else{
        cout << "NA\n";
    }
    return 0;
}



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

int main()
{
	int x, y;

	for (int i = 0;; i++){

		cin >> x >> y;

		if (x == 0 && y == 0)
			break;

		if (x >= y)
			cout << y << " " << x << endl;
		else
			cout << x << " " << y << endl;
	}

	return 0;
}

Measured memory_bytes: 2996
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

var (
	MAX      = 500000
	SENTINEL = 2000000000
	cnt      = 0
	L, R     = make([]int, MAX+2), make([]int, MAX+2)
)

func main() {
	fmt.Println(answer(os.Stdin))
}

func answer(r io.Reader) string {
	n := 0

	sc := bufio.NewScanner(r)
	sc.Split(bufio.ScanWords)
	sc.Scan()
	n, _ = strconv.Atoi(sc.Text())
	A := make([]int, n)
	for i := 0; i < n; i++ {
		sc.Scan()
		A[i], _ = strconv.Atoi(sc.Text())
	}

	mergeSort(A, n, 0, n)

	result := strings.TrimRight(fmt.Sprintf("%+v", A)[1:], "]") + "\n"
	return result + strconv.Itoa(cnt)
}

func merge(A []int, n, left, mid, right int) {
	n1 := mid - left
	n2 := right - mid
	for i := 0; i < n1; i++ {
		L[i] = A[left+i]
	}
	for i := 0; i < n2; i++ {
		R[i] = A[mid+i]
	}
	L[n1], R[n2] = SENTINEL, SENTINEL

	i, j := 0, 0
	for k := left; k < right; k++ {
		cnt++
		if L[i] <= R[j] {
			A[k] = L[i]
			i++
			continue
		}
		A[k] = R[j]
		j++
	}
}

func mergeSort(A []int, n, left, right int) {
	if left+1 < right {
		mid := (left + right) / 2
		mergeSort(A, n, left, mid)
		mergeSort(A, n, mid, right)
		merge(A, n, left, mid, right)
	}
}



Measured memory_bytes: 50800
#include <stdio.h>
#include <stdlib.h>
#define MAX 2000001
#define VMAX 10000

int main(){
  unsigned short *A, *B;
  int C[VMAX+1];
  int n, i;

  scanf("%d", &n);

  A = malloc(sizeof(short)*n+1);
  B = malloc(sizeof(short)*n+1);
  for(i=0;i<=VMAX;i++) C[i] = 0;
  
  for(i=0;i<n;i++){
      scanf("%hu",&A[i+1]);
      C[A[i+1]]++;
  }
  
  for(i=1;i<=VMAX;i++) C[i] = C[i] + C[i - 1];
  for(i=1;i<=n;i++){
      B[C[A[i]]] = A[i];
      C[A[i]]--;
  }
  
  for(i=1;i<=n;i++){
      if(i>1) printf(" ");
      printf("%d",B[i]);
  }
  printf("\n");
  
  return 0;
}


Measured memory_bytes: 9656
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <map>
#include <cstdlib>
using namespace std;

typedef long long ll;

int main()
{
    int N,M;
    cin >> N >> M;
    vector < int > s[M];
    for(int i=0; i<M; i++){
        int k;
        cin >> k;
        for(int j=0; j<k; j++){
            int tmp;
            cin >> tmp;
            tmp--;
            s[i].push_back(tmp);
        }
    }
    vector<int> p(M);
    for(int i=0; i<M; i++){
        cin >> p[i];
    }
    
    int ans=0;
    vector<int> flag(N);
    fill(flag.begin(), flag.end(), 0);
    int limit=pow(2, N);
    
    for(int i=0; i<limit; i++){
        int tmp=i;
        for(int j=0; j<N; j++){
            flag[j]=tmp%2;
            tmp/=2;
        }
        bool ok=true;
        for(int j=0; j<M; j++){
            int sumation=0;
            for(int s_num=0; s_num<s[j].size(); s_num++){
                if(flag[s[j][s_num]]==1) sumation++;
            }
            if(sumation%2!=p[j]){
                ok=false;
                break;
            }
        }
        if(ok) ans++;
    }

    cout << ans << endl;
    
    

    return 0;
}

Measured memory_bytes: 384
import sys
N = int(input())
array = list(map(int,input().split()))

if not ( 2 <= N <= 10**5 ): sys.exit()
if not ( 0 <= min(array) and max(array) <= 10**18): sys.exit()
if 0 in array: print(0); sys.exit()

sum = array[0]
for I in range(1,len(array)):
    sum *= array[I]
    if sum > 10**18: print(-1);sys.exit()
print(sum)

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

int main() {
  int n, k, s;
  cin >> n >> k >> s;
  rep(i,n){
    if(i < k){
      cout << s << (i == n - 1 ? "\n" : " ");
    }else {
      if(s == 1000000000){
        cout << s - 1 << (i == n - 1 ? "\n" : " ");
      }else {
        cout << s + 1 << (i == n - 1 ? "\n" : " ");
      }
    }
  }
  return 0;
}

Measured memory_bytes: 1280
# coding:utf-8

INF = float('inf')


def inpl(): return list(map(int, input().split()))


N = int(input())
A = inpl()

n = max(A)
r = max(A)
tmp = 0
for i in range(N):
    a = A[i]
    if a == n: continue
    if a < n - a: a = n - a
    if tmp <= n - a:
        r = A[i]
        tmp = n - a

print(n, r)

Measured memory_bytes: 14428
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>

using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define INF (1e9)

int X;
vector<bool> isPrime;
void calcPrime(int max) {
    isPrime = vector<bool>(max + 1, true);
    isPrime[0] = false;
    isPrime[1] = false;
    for (int i = 4; i <= max; i += 2)
        isPrime[i] = false;
    for (int i = 3; i * i <= max; i += 2) {
        if (!isPrime[i]) continue;
        for (int j = i * i; j <= max; j += i)
            isPrime[j] = false;
    }
}
int main() {
    cin >> X;

    calcPrime(X + 100);

    int ans;

    for (int i = X; i < X + 100; i++) {
        if (isPrime[i]) {
            cout << i << endl;
            return 0;
        }
    }

    return 0;
}


Measured memory_bytes: 256
/*
 * @Author: Kaizyn
 * @Date: 2020-03-07 21:10:26
 * @LastEditors: Kaizyn
 * @LastEditTime: 2020-03-07 21:13:56
 * @FilePath: \Code\atcoder\abc158A.cpp
 */
#include <bits/stdc++.h>

// #define DEBUG

using namespace std;

const int N = 10;
const int MOD = 1e9+7;
const double eps = 1e-7;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

int a, b;
string s;

inline void solve()
{
    cin >> s;
    for (char c : s) {
        if (c == 'A') ++a;
        else ++b;
    }
    cout << (a && b ? "Yes" : "No") << endl;
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int testcase = 1;
    // cin >> testcase;
    for (int i = 1; i <= testcase; ++i) {
        solve();
    }
    return 0;
}

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

int main(int argc, const char * argv[]) {
    int x,y;
    int size,length;
    
    cin >> x;
    cin >> y;
    
    size = x * y;
    length = 2 * x + 2 * y;
    
    cout << size << " " << length << endl;
    
    return 0;
}


Measured memory_bytes: 3000
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        int n, m;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        int[] p = new int[m];
        String[] s = new String[m];
        for (int i = 0; i < m; i++) {
            p[i] = sc.nextInt();
            s[i] = sc.next();
        }

        int clear = 0;
        int fault = 0;
        int[] flg = new int[n+1];
        int[] flgFault = new int[n+1];
        for (int i = 0; i < m; i++) {
            if (s[i].equals("AC") && flg[p[i]] != 1) {
                flg[p[i]] = 1;
                clear++;
            } else {
                if (s[i].equals("WA") && flg[p[i]] != 1) {
                    flgFault[p[i]]++;
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            if (flg[i] == 1) {
                fault += flgFault[i];
            }
        }

        System.out.println(Integer.toString(clear) + " " + Integer.toString(fault));
    }
}

Measured memory_bytes: 69808
#include <iostream>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e18;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 20000;
constexpr ll nx[8] = {1,0,-1,0,-1,-1,1,1};
constexpr ll ny[8] = {0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    vector<ll> a(n);
    cins(all(a));
    RSORT(a);
    ll cnt = 0,p,q,i = 0;
    while(i < n){
        if (a[i] == a[i+1]){
            if (cnt == 0){
                p = a[i];
                cnt++;
                i += 2;
            }
            else if (cnt == 1){
                q = a[i];
                cnt++;
                break;
            }
        }
        else i++;
    }
    if (cnt < 2) PRINT(0);
    else PRINT(p*q);
}


Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        final Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int n = in.nextInt();
        int k = in.nextInt();
        double[] all = new double[n];
        for (int i = 0; i < n; i++) {
            int p = in.nextInt();
            all[i] = (1 + p) * p / (double) 2 / (double) p;
        }

        double current = 0;

        for (int i = 0; i < k; i++) {
            current += all[i];
        }
        double max = current;
        for (int i = k; i < n; i++) {
            current = current - all[i - k] + all[i ];
            max = Double.max(current, max);
        }
        System.out.println(max);
    }
}


Measured memory_bytes: 73948
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

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

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

ll calc(ll x){
    if (x == 1) return 1;
    return 2 * calc(x / 2) + 1;
}

int main() {
    int h, n;
    cin >> h >> n;
    VI a(n), b(n);
    REP(i,n){
        a[i] = in();
        b[i] = in();
    }
    VI dp(h + 1, 1e9);
    dp[h] = 0;
    REP(i,n){
        FORR(j,h,0){
            int k = max(0, j - a[i]);
            chmin(dp[k], dp[j] + b[i]);
        }
    }
    cout << dp[0] << endl;
    return 0;
}


Measured memory_bytes: 256
def floor(a, b):
  # return int((a - a%b)/b)
  return a//b
def gcd(a, b):
  while b != 0:
      a, b = b, a % b
  return a
def lcm(a, b):
  return floor((a * b), gcd(a, b))
input = list(map(int, input().split(' ')))
total_count = input[1] + 1 - input[0]
div_c = floor(input[1], input[2]) - floor(input[0] -1, input[2])
div_d = floor(input[1], input[3]) - floor(input[0] -1, input[3])
div_cd = floor(input[1], lcm(input[2], input[3])) - floor(input[0] -1, lcm(input[2], input[3]))
print(total_count - (div_c + div_d - div_cd))

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

int main(){
    long long int a,b;

    cin >> a >> b;

    if( ( a == 1 ) || ( b == 1) ){
        cout << 1 << "\n";
    }
    else{
        cout << ( ( a * b ) + 1 ) / 2 << "\n";
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
string s;
int l,k,ans,c,n;

int main ()
{
    cin >> n >> k >> s;
    for(int r = 0;r < n;r++)
    {
        if(s[r]== '0' )
        {
            if(r == 0 || s[r-1] == '1') c++;
        }
        if (c > k)
        {
            while(s[l] == '1') l++;
            while(s[l] == '0') l++;
            c--;
        }
        ans = max(ans,r-l+1);
    }
    cout << ans;
}


Measured memory_bytes: 512
N = int(input())

l = []
for i in range(N):
    text = input()
    l.append(text)

print("AC" + " x " + str(l.count("AC")))
print("WA" + " x " + str(l.count("WA")))
print("TLE" + " x " + str(l.count("TLE")))
print("RE" + " x " + str(l.count("RE")))

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

int main(void)
{
    int N,K,tmp,sum = 0;
    cin >> N >> K;

    vector<int> A(N);

    rep(i, N){
        cin >> tmp;
        A[tmp-1]++;
    }

    sort(A.begin(),A.end(),greater<int>());

    rep(i,K){
        sum += A[i];
    }

    cout << N-sum << endl;

    return 0;
}

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

char s[65536];
char t[65536];

int main(void)
{
	int n;
	while(scanf("%d", &n), n){
		int i;
		char* str = s;
		char* tmp = t;
		scanf("%s", s);
		
		for(i=0; i<n; ++i){
			int m = strlen(str);
			int read = 0;
			int write = 0;
			while(read<m){
				char num = str[read];
				int cnt;
				
				for(cnt=0; str[read+cnt]==num; ++cnt);
				sprintf(tmp+write, "%d\0", cnt);
				
				while(tmp[write] != '\0')
					++write;
				
				tmp[write] = num;
				++write;
				read += cnt;
			}
			tmp[write] = '\0';
			
			{
				char* hoge = str;
				str = tmp;
				tmp = hoge;
			}
		}
		puts(str);
	}
	
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,k;
	scanf("%d %d %d\n%d",&a,&b,&c,&k);
	if(c<a)
	{
		c+=a;
		a=c-a;
		c-=a;
	}
	if(c<b)
	{
		c+=b;
		b=c-b;
		c-=b;
	}
	if(b<a)
	{
		b+=a;
		a=b-a;
		b-=a;
	}
	c=c<<k;
	printf("%d",a+b+c);
	return 0;
}

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

int main() {
  int N,K;
  cin>>N>>K;
  int ans=1;
  for(int i=0;i<N;i++){
    if(ans+K>ans*2){
      ans=ans*2;
    }
    else{
      ans=ans+K;
    }
  }
  cout<<ans<<endl;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define IFOR(i, m, n) for(ll i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()

const ll INF = 1e18;
struct Edge {
  ll to, cost;  // 辺の接続先頂点, 辺の重み
  Edge(ll to, ll cost) : to(to), cost(cost) {}  // コンストラクタ
};

typedef vector<vector<Edge> > AdjList;  // 隣接リストの型
AdjList graph;  // グラフの辺を格納した構造体
                // graph[v][i]は頂点vから出るi番目の辺Edge
AdjList revgraph;
vector<ll> dist; // 最短距離
vector<int> cycle; // 負閉路上の点か

// 戻り値がtrueなら負の閉路を含む
bool bellman_ford(ll n, ll s) { // nは頂点数、sは開始頂点
  bool f = false;
  dist = vector<ll>(n, INF);
  dist[s] = 0; // 開始点の距離は0
  REP(i,n) REP(v,n) REP(k,graph[v].size()){
    Edge e = graph[v][k];
    if (dist[v] != INF && dist[e.to] > dist[v] + e.cost) {
      dist[e.to] = dist[v] + e.cost;
      if (i == n - 1){
        f =  true; // n回目にも更新があるなら負の閉路が存在
        cycle[v] = 1;
      }
    }
  }
  return f;
}

void dfs(ll v, AdjList& g, vector<int>& reach){
  if(reach[v]) return;
  reach[v] = 1;
  FOREACH(e,g[v]){
    dfs(e.to, g, reach);
  }
}

int main(){
  ll n,m; cin >> n >> m;
  graph = AdjList(n);
  revgraph = AdjList(n);
  cycle = vector<int>(n);
  vector<int> reach_s(n,0),reach_t(n,0);
  REP(i,m){
    ll a,b,c; cin >> a >> b >> c;
    a--; b--;
    revgraph[b].push_back(Edge(a,1));
    c *= -1;
    graph[a].push_back(Edge(b,c));
  }
  bool f = bellman_ford(n, 0);
  //負閉路あり
  if(f) {
    dfs(0, graph,reach_s);
    dfs(n-1, revgraph, reach_t);
    //負閉路を経由して頂点n-1へ行けるとき
    REP(i,n) if(reach_s[i] & cycle[i] & reach_t[i]){
      cout << "inf" << endl;
      return 0;
    }
  }
  cout << -dist[n-1] << endl;
}



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

using namespace std;

int main() {
	stack<int> stack;
	string input;
	while (cin >> input) {
		if (input == "+") {
			int post = stack.top(); stack.pop();
			int pre = stack.top(); stack.pop();

			stack.push(pre + post);
		}
		else if (input == "-") {
			int post = stack.top(); stack.pop();
			int pre = stack.top(); stack.pop();

			stack.push(pre - post);
		}
		else if (input == "*") {
			int post = stack.top(); stack.pop();
			int pre = stack.top(); stack.pop();

			stack.push(pre * post);
		}
		else {
			stack.push(atoi(input.c_str()));
		}
	}
	cout << stack.top() << endl;

	}

Measured memory_bytes: 1200
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main(){
	string str;
	while(getline(cin,str) && str != "."){
		vector<char> c;
		for(int i = 0 ; i < str.size() ; i++)
			if(str[i] == ')' || str[i] == '(' || str[i] == '[' || str[i] == ']')
				c.push_back(str[i]);
		stack<char> s;
		bool f = true;
		for(int i = 0 ; i < c.size() ; i++){
			if(s.size() == 0 || c[i] == '(' || c[i] == '[')
				s.push(c[i]);
			else if( (s.top() == '(' && c[i] == ')') || (s.top() == '[' && c[i] == ']') ){
				s.pop();
			}else{
				f = false;
				break;
			}
		}
		cout << (f && s.empty() ?"yes":"no") << endl;
	}
}

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



int main() {
  int N;
  cin >> N;
  
  vector<int> A(N);
  for(int i=0;i<N;i++){
    cin >> A.at(i);
  }
  
  
  sort(A.begin(), A.end());
  
  bool flag = false;
  for(int i=0;i<N-1;i++){
    if(A.at(i)==A.at(i+1))
       flag=true;
       }  
  
  
  if(flag)
    cout << "NO" << endl;
  else
    cout << "YES" << endl;
  
}


Measured memory_bytes: 1024
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int sum = 0;
		int[] list = new int[3];
		list[0] = scan.nextInt();
		list[1] = scan.nextInt();
		list[2] = scan.nextInt();
		Arrays.sort(list);
		sum = list[0] + list[1];
		System.out.println(sum);
		
		scan.close();
	}

}


Measured memory_bytes: 21716
#include<cstring>
#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
#include<cmath>
#include<sstream>
#include<cassert>
#include<string>
#include<algorithm>
#define rep(i,n) for(int i = 0;i<n;i++)
#define Rep(i,n) for(int i = 1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define mult(a,b) (((a)*(b))%MOD)
#define se second
#define INF 1300000
#define MOD 1000000007
using namespace std;
typedef long long int ll;

vector<int> G[100000];
int V,E;
vector<int> order;
bool visited[100000];

void dfs(int now){
    visited[now]=1;
    rep(i,G[now].size()){
        if(!visited[G[now][i]]){
            dfs(G[now][i]);
        }
    }
    order.pb(now);
    return;
}

int main(){
    cin>>V>>E;
    rep(i,E){
        int a,b;
        cin>>a>>b;
        G[a].pb(b);
    }
    rep(i,V){
        if(!visited[i])
            dfs(i);
    }
    reverse(order.begin(),order.end());
    rep(i,V){
        cout<<order[i]<<endl;
    }
}

Measured memory_bytes: 4068
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;

#define rep(i, n) for (int i = 0; i < n; ++i)
#pragma region Debug
template <typename T>
void view(const std::vector<T> &v)
{
    for (const auto &e : v)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;
}
template <typename T>
void view(const std::vector<std::vector<T>> &vv)
{
    for (const auto &v : vv)
    {
        view(v);
    }
}
#pragma endregion

int main()
{
    string s;
    cin >> s;
    rep(i, s.size()) cout << "x";
    cout << endl;
    return 0;
}

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

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

    int count = 0;

    for (int x = 0; x <= K; x++) {
        for (int y = 0; y <= K; y++) {
            int num = S - (x + y);
            if (0 <= num && num <= K) {
                count++;
            }
        }
    }

    cout << count << endl;

    return 0;
}

Measured memory_bytes: 3624
import java.util.*;
public class Main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int p[] = new int[n];
    int total = 0;
    for(int i=0 ; i<n ; i++){
      p[i] = sc.nextInt();
    }
    Arrays.sort(p);
    for(int i=0 ; i<n-1 ; i++){
      total = total + p[i];
    }
    total = total + (p[n-1]/2);
    System.out.println(total);
  }
}


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

struct Node
{
    int key;
    Node *p, *l, *r;
};

Node *root, *NIL;

void insert(int k) {
    Node *tmp_p = NIL;
    Node *tmp = root;
    Node *z;

    // z = (Node *)malloc(sizeof(Node));
    z = new Node;
    z->key = k;
    z->l = NIL;
    z->r = NIL;

    while (tmp != NIL) {
        tmp_p = tmp;
        if (z->key < tmp->key) {
            tmp = tmp->l;
        }
        else {
            tmp = tmp->r;
        }
    }

    z->p = tmp_p;
    if (tmp_p == NIL) {
        root = z;
    }
    else {
        if (z->key < tmp_p->key) {
            tmp_p->l = z;
        }
        else {
            tmp_p->r = z;
        }
    }
}

Node * find(int k, Node *u) {
    while (u != NIL && k != u->key)
    {
        if (k < u->key)
        {
            u = u->l;
        }
        else
        {
            u = u->r;
        }
    }
    return u;
}

void inorder(Node *u) {
    if (u == NIL) {
        return;
    }

    inorder(u->l);
    cout << " " << u->key;
    inorder(u->r);
}

void preorder(Node *u) {
    if (u==NIL) {
        return;
    }

    cout << " " << u->key;
    preorder(u->l);
    preorder(u->r);
}


Node * treeMinimum(Node *x) {
    while (x->l != NIL) {
        x = x->l;
    }
    return x;
}


Node * treeSuccessor(Node *x) {
    if (x->r != NIL)
        return treeMinimum(x->r);
    Node *y = x->p;
    while ( y != NIL && x == y->r) {
        x = y;
        y = y->p;
    }
    return y;
}

void treeDelete(Node *z) {
    Node *y; // for delete
    Node *x; // chilf of y

    if ( z->l == NIL || z->r ==NIL )
        y = z;
    else
    {
        y = treeSuccessor(z);
    }

    // decide y's child x
    if (y->l != NIL) // yに左の子があれば, xはyのleft child
    {
        x = y->l;
    }
    else // そうでなければxはyのright child
    {
        x = y->r;
    }

    if ( x != NIL) {  // xが存在するならばxの親をyの親とする
        x->p = y->p;
    }

    if (y->p == NIL)
    { // if y is root, x become root;
        root = x;
    }
    else
    {
        if (y == y->p->l) {  // if y is left child
            y->p->l = x;
        }
        else // if y is right child
        {
            y->p->r = x;
        }
    }

    if (y != z) {   // zの次接点が削除された場合
        z->key = y->key;  // yのデータをzにコピー
    }

    free(y);
}

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

    string cmd;
    int k;
    for (int i = 0; i < N; i++)
    {
        cin >> cmd;
        if (cmd == "insert") {
            cin >> k;
            insert(k);
        }
        else if (cmd == "find")
        {
            cin >> k;
            Node *t = find(k, root);
            if (t != NIL)
                cout << "yes" << endl;
            else
            {
                cout << "no" << endl;
            }
        }
        else if (cmd == "print")
        {
            inorder(root);
            cout << endl;
            preorder(root);
            cout << endl;
        }
        else if (cmd == "delete")
        {
            cin >> k;
            treeDelete(find(k, root));
        }
        }
}


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

#define endl '\n'

typedef long long ll;
typedef pair<int, int> pii;

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

	vector<int> v(3);
	for(auto &el : v) cin >> el;

	int k; cin >> k;
	cout << accumulate(v.begin(), v.end(), 0) + *max_element(v.begin(), v.end()) * ((1 << k) - 1) << endl;

	return 0;
}


Measured memory_bytes: 256
import sys

A, B, C, K = map(int, input().split())

ans = 0

if A >= K:
    print(K)
    sys.exit()
else:
    ans += A
    K -= A

if B >= K:
    print(ans)
    sys.exit()
else:
    K -=B

ans -= K
print(ans)

Measured memory_bytes: 9192
import sys
def input(): return sys.stdin.readline().rstrip()
from operator import itemgetter
def main():
    n,m=map(int,input().split())
    A=[int(_) for _ in input().split()]
    A.sort()
    D=[]
    for i in range(m):
        b,c=map(int,input().split())
        D.append([b,c])
    D.sort(key=itemgetter(1),reverse=True)
    len_D=len(D)
    index_d=0
    for i in range(n):
        if D[index_d][0]==0:
            index_d+=1
            if index_d==len_D:
                break
        if A[i]>=D[index_d][1]:
            break
        A[i]=D[index_d][1]
        D[index_d][0]-=1
    print(sum(A))

if __name__=='__main__':
    main()

Measured memory_bytes: 25644
#include <bits/stdc++.h>
#include <boost/range/adaptor/reversed.hpp>
#include <boost/range/algorithm/sort.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using boost::irange;
using boost::sort;
using boost::adaptors::reversed;

struct mint {
    static constexpr long MOD = 1'000'000'007;
    long value;

    constexpr mint(long value = 0) noexcept : value((value % MOD + MOD) % MOD) {}
    constexpr mint operator-() const noexcept {
        return mint(-value);
    }
    constexpr mint& operator+=(const mint& rhs) noexcept {
        if ((value += rhs.value) >= MOD) value -= MOD;
        return *this;
    }
    constexpr mint& operator-=(const mint& rhs) noexcept {
        if ((value += MOD - rhs.value) >= MOD) value -= MOD;
        return *this;
    }
    constexpr mint& operator*=(const mint& rhs) noexcept {
        (value *= rhs.value) %= MOD;
        return *this;
    }
    constexpr mint operator+(const mint& rhs) const noexcept {
        mint res(*this);
        return res += rhs;
    }
    constexpr mint operator-(const mint& rhs) const noexcept {
        mint res(*this);
        return res -= rhs;
    }
    constexpr mint operator*(const mint& rhs) const noexcept {
        mint res(*this);
        return res *= rhs;
    }
    constexpr mint pow(long e) const noexcept {
        if (e == 0) return 1;
        mint a = pow(e >> 1);
        a *= a;
        if (e % 2 == 1) a *= *this;
        return a;
    }
    constexpr mint inv() const noexcept {
        return pow(MOD - 2);
    }
    constexpr mint& operator/=(const mint& rhs) noexcept {
        return *this *= rhs.inv();
    }
    constexpr mint operator/(const mint& rhs) const noexcept {
        mint res(*this);
        return res /= rhs;
    }
    friend constexpr mint pow(const mint& a, const long& b) noexcept {
        return a.pow(b);
    }
    friend ostream& operator<<(ostream& os, const mint& n) noexcept {
        os << n.value;
        return os;
    }
};

int main() {
    int n, k;
    cin >> n >> k;
    mint ans = 0;
    for (int i = k; i <= n + 1; i++) ans += (mint)i * (n - i + 1) + 1;
    cout << ans << endl;
}


Measured memory_bytes: 3640
N,K = list(map(int,input().split()))
# N = random.randint(1,20)
# K = random.randint(1,N)
# print(N,K)

p=(10**9)+7

def get_mod_factalize(A):
    a_mod = 1     
    for a in range(1,A+1):
        a_mod = a * a_mod % p
    return a_mod

def get_mod_comb(A,B):
    a_mod = get_mod_factalize(A)
    b_mod = get_mod_factalize(B)
    a_b_mod = get_mod_factalize(A-B)

    return (a_mod * pow((b_mod*a_b_mod),p-2,p))%p

a = N-K
b = K

for i in range(1,K+1): 
    if i > a+1 :
        ans=0
    else:
        ans=(get_mod_comb(a+1,i) * get_mod_comb(b-1,i-1))%p
    print(ans)

Measured memory_bytes: 74472
using System;
using System.Collections.Generic;
using System.Text;

namespace AtTest.ABC_112
{
  class D
  {
    static void Main(string[] args)
    {
      Method(args);
      Console.ReadLine();
    }

    static void Method(string[] args)
    {
      long[] nm = ReadLongs();
      long n = nm[0];
      long m = nm[1];

      long max = (int)Math.Sqrt(m);
      long divider = 1;
      for (long i = max; i >= 1; i--)
      {
        if (m % i == 0)
        {
          if (m / i <= m / n)//-> n <= i
          {
            divider = Math.Max(m / i, divider);
          }
          else if (i <= m / n)
          {
            divider = Math.Max(i, divider);
          }
        }
      }
      Console.WriteLine(divider);
    }

    private static string Read() { return Console.ReadLine(); }
    private static int ReadInt() { return int.Parse(Read()); }
    private static long ReadLong() { return long.Parse(Read()); }
    private static double ReadDouble() { return double.Parse(Read()); }
    private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
    private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
    private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
  }
}

Measured memory_bytes: 13140
#include <algorithm>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <tuple>
#include <vector>

using namespace std;

typedef long long ll;
constexpr ll MOD = 1000000007;

// struct UnionFind {
//     vector<int> par;
    
//     UnionFind(int N): par(N) {
//         for (int i=0;i<N;i++) par[i] = i;
//     }

//     int root(int x) {
//         if (par[x] == x) return x;
//         else return par[x] = root(par[x]);
//     }

//     void unite(int x, int y) {
//         int rx = root(x);
//         int ry = root(y);
//         if (rx == ry) return;
//         par[rx] = ry;
//     }

//     bool same(int x, int y) {
//         int rx = root(x);
//         int ry = root(y);
//         return rx == ry;
//     }
// };

int main(void) {
    int N;
    vector<int> A(200010,0), L(200010,0), R(200010,0);
    cin >> N;
    for (int i=0;i<N;i++) cin >> A[i];
    L[0] = A[0];
    for (int i=1;i<N;i++) L[i] = max(L[i-1],A[i]);
    R[N-1] = A[N-1];
    for (int i=N-2;i>=0;i--) R[i] = max(R[i+1],A[i]);

    cout << R[1] << endl;
    for (int i=1;i<N-1;i++) {
        cout << max(L[i-1],R[i+1]) << endl;
    }
    cout << L[N-2] << endl;

    return 0;
}


Measured memory_bytes: 3968
#N=int(input())
N,M = map(int,input().split())
#N=int(input())
H = list(map(int,input().split()))
#S=str(input())
flag=[1]*N
line=[]
for i in range(M):
    a,b = map(int,input().split())
    if H[a-1]<H[b-1]:
        flag[a-1]=0
    elif H[a-1]==H[b-1]:
        flag[a-1]=0
        flag[b-1]=0
    else:
        flag[b-1]=0
print(sum(flag))


Measured memory_bytes: 19968
#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N;
	cin >> N;
	vector<int> A(N);
	for(int i =0; i < N; i++) cin >> A[i];
	vector< vector<int> > G(N);
	for(int i =0; i < N-1; i++) {
		int a,b;
		cin >> a >> b;
		G[--a].push_back(--b);
		G[b].push_back(a);}
	vector<bool> live(N,true);
	vector<int> L;
	for(int i =0; i < N; i++) if(G[i].size() == 1) L.push_back(i);
	vector<int> S(N,0),D(N);
	vector< vector<int> > Sv(N);
	for(int i =0; i < N; i++) D[i] =G[i].size();
	int n =L.size();
	while(!L.empty()) {
		if(n == N) {
			if((int)L.size() == 2) {
				if(A[L[0]] == A[L[1]]) cout << "YES\n";
				else cout << "NO\n";}
			else {
				if(A[L[0]] == 0) cout << "YES\n";
				else cout << "NO\n";}
			return 0;}
		ALL_THE(L,it) live[*it] =false;
		vector<int> Ln;
		ALL_THE(L,it) {
			ALL_THE(G[*it],jt) {
				D[*jt]--;
				S[*jt] +=A[*it];
				Sv[*jt].push_back(A[*it]);
				if(D[*jt] == 1 && live[*jt]) Ln.push_back(*jt);}
			}
		ALL_THE(Ln,it) {
			int a =S[*it]-A[*it], b =2*A[*it]-S[*it];
			if(a < 0 || b < 0 || 2*a > S[*it]) {
				cout << "NO\n";
				return 0;}
			sort(begin(Sv[*it]),end(Sv[*it]));
			if(a > S[*it]-Sv[*it].back()) {
				cout << "NO\n";
				return 0;}
			A[*it] =b;}
		n +=Ln.size();
		L =Ln;}
	cout << "YES\n";
	return 0;}

// look at my code
// my code is amazing


Measured memory_bytes: 12796
/*CODE BY VIJAY MUKHIJA*/
#include<bits/stdc++.h>
#define lli long long int
#define ld long double
#define fi first
#define se second
#define pb push_back
#define MOD 1000000007
#define SMOD 998244353
#define what_is(x) cout << #x << " is " << x << endl
#define what_are(x,y) cout<< #x <<" is " << x << " "<< #y <<" is " << y <<endl
using namespace std;
lli Powerm(lli a,lli b,lli m){ if(b==0) return 1; if(b==1) return a%m; lli t=Powerm(a,b/2,m); t=(t*t)%m; if(b&1)t=(t*a)%m; return t;}
lli Power(lli a,lli b){ if(b==0) return 1; if(b==1) return a; lli t=Power(a,b/2); t=(t*t); if(b&1)t=(t*a); return t;}
lli Gcd(lli a,lli b) { if(b==0) { return a; } else { return Gcd(b,a%b); } }
lli LeftMostSetBit(lli n){ if (n == 0){return 0; } lli msb = 0; while (n != 0) {n = n / 2; msb++; } return msb; }
lli RightMostSetBit(lli n){ return __builtin_ffsl(n); }
lli llsqrt(lli x){ if(x==0 || x==1) return x; lli start=1, end=x/2, ans; while(start<=end) { lli mid=(start+end)/2; if(mid*mid==x) return mid;
else if(mid <= x/mid) ans=mid,start=mid+1; else end=mid-1; }  return ans; }

int main()
{
	// #ifndef ONLINE_JUDGE
 //    	freopen("input.txt", "r", stdin);
 //    	freopen("output.txt", "w", stdout);
	// #endif
	lli n,k;
	cin>>n>>k;
	lli a[n];
	for(lli i=0;i<n;i++)
	{
		cin>>a[i];
	}
	//bottomup
	lli dp[n+1];
	memset(dp,INT_MAX,sizeof(dp));
	dp[1]=0;
	dp[2]=abs(a[1]-a[0]);
	for(lli i=2;i<n;i++)
	{
		lli ans=INT_MAX;
		for(lli j=i-1;j>=max(i-k,(lli)0);j--)
		{
			ans=min(ans,abs(a[i]-a[j])+dp[j+1]);
		}
		dp[i+1]=ans;
	}
	cout<<dp[n]<<endl;

}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
int main(){
    int A,B,C,D,E,F,G=0,H=0,I=0;
    cin >> A >> B >> C;
    for(int i=0;i<A;i++){
        cin >> D;
        if(D>=B&&D<C)continue;
        G++;
    }
    cout << G << endl;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def Z(s):
    """
    s: str
    return list of int with length len(s)
    """
    # initialization
    n=len(s)
    z=[0]*n
    z[0]=n
    # construct
    L,R=0,0
    for i in range(1,n):
        if i>=R: # 過去の結果が全く使えない
            L=R=i
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
        elif z[i-L]<R-i: # 過去の結果が全て使える
            z[i]=z[i-L]
        else: # 過去の結果が一部使える
            L=i
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
    return z
def resolve():
    n=int(input())
    s=input()
    ans=0
    for i in range(n):
        z=Z(s[i:])
        k=len(z) # k=n-i
        for j in range(k):
            ans=max(ans,min(j,z[j]))
    print(ans)
resolve()

Measured memory_bytes: 48092
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author silviase
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        binarySearch solver = new binarySearch();
        solver.solve(1, in, out);
        out.close();
    }

    static class binarySearch {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = in.nextInt();
            int q = in.nextInt();
            int cnt = 0;
            for (int i = 0; i < q; i++) {
                int key = in.nextInt();
                int ng = -1;
                int ok = a.length;
                while (Math.abs(ok - ng) > 1) {
                    int mid = (ok + ng) / 2;
                    if (a[mid] >= key) {
                        ok = mid;
                    } else {
                        ng = mid;
                    }
                }
                if (a[ok] == key) cnt++;
            }
            out.println(cnt);
        }

    }
}




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

#define LL long long

const int CN = 2e5+5;

LL a[CN],b[CN],n,k;

bool cmp(LL x,LL y) {return x>y;}

bool checker(LL x){LL t=k;for(int i=1;i<=n;i++)t-=max(0ll,a[i]-x/b[i]);return t>=0;}

int main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
	
	sort(a+1,a+n+1,cmp); sort(b+1,b+n+1);
	
	LL l = 0,r = 1e12;
	while(l < r){
		LL m = (l + r) >> 1;
		if(checker(m)) r = m;
		else l = m + 1;
	}
	
	printf("%lld",r);
}

Measured memory_bytes: 3328
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>
#include<bits/stdc++.h>
using namespace std;
int n,a[44],b[44],c[44],sa,sb,ma,mb,ans=1e9,dp[44][444][444];
int main()
{
	cin>>n>>ma>>mb;
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=400;j++)
		{
			for(int k=0;k<=400;k++)
			{
				dp[i][j][k]=1e9;
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		cin>>a[i]>>b[i]>>c[i];
		sa+=a[i];
		sb+=b[i];
	}
	dp[0][0][0]=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<=400;j++)
		{
			for(int k=0;k<=400;k++)
			{
				if(dp[i][j][k]==1e9)
				{
					continue;
				}
				dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k]);
				dp[i+1][j+a[i]][k+b[i]]=min(dp[i+1][j+a[i]][k+b[i]],dp[i][j][k]+c[i]);
			}
		}
	}
	for(int i=1;i<=400;i++)
	{
		for(int j=1;j<=400;j++)
		{
			if(i*mb==j*ma)
			{
				ans=min(ans,dp[n][i][j]);
			}
		}
	}
	if(ans==1e9)
	{
		cout<<-1<<endl;
	}
	else
	{
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 32896