akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < n; ++i)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=1e18;

P f(ll n,ll c){
  ll s=n/c;
  ll q=n-(s*c);
  P ans=make_pair(s,q);
//  cout<<"n"<<n<<"s"<<s<<"q"<<q<<endl;
  return ans;

  }


int main() {
  ll n;
  cin>>n;
  vector<ll> a(n);
  rep(i,n)cin>>a[i];
  ll cost=a[0];
  ll kabu=0;
  ll money=1000;
  rep(i,n-1){
    if (a[i+1]>cost){
      P temp=f(money,cost);
      kabu+=temp.first;
      money=temp.second;
      ll now=kabu*a[i+1];
      kabu=0;
      money+=now;
    }

    else if (a[i+1]<cost){
      ll now=kabu*cost;
      kabu=0;
      money+=now;
      P temp=f(money,a[i+1]);
      kabu+=temp.first;
      money=temp.second;

  }
  cost=a[i+1];
//  cout<<money<<" "<<kabu<<endl;
}

ll ans=money+(kabu*cost);
cout<<ans;
}


Measured memory_bytes: 3580
#include<iostream>
#include<vector>
#include<math.h>
#include<bits/stdc++.h>
#define lli long long int
#define mod 1000000007
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false); 
//    cin.tie(NULL); 
    cout.tie(NULL);
  	string s;
  	cin>>s;
  	set<char>st;
  	for(int i=0;i<s.length();i++)
  		st.insert(s[i]);
  	if(st.size()>1)
  		cout<<"Yes";
  	else
  		cout<<"No";
	return 0;
}


Measured memory_bytes: 256
<?php
fscanf(STDIN,"%d",$N);
fscanf(STDIN,"%d",$K);

$board = 1;
$plusJudge = false;
for($i=0;$i<$N;$i++){
  if($plusJudge){
    $board += $K;
  }else{
    if($board*2 >= $board+$K){
      $board += $K;
      $plusJudge = true;
    }else{
      $board *= 2;
    }
  }
}
echo $board;

Measured memory_bytes: 3704
fun str() = readLine()!!
fun int() = str().toInt()
fun long() = str().toLong()

fun read(d:String = " ") = str().split(d)
fun <T> list(d:String = " ",f:String.()->T) = read(d).map {f(it)}
fun list() = list {toInt()}

fun <T> MutableList<T>.removeLast() = this.removeAt(this.lastIndex)

const val mod = 1000000007L

fun modpow(n:Long,p:Long = mod-2L):Long = when {
	p==0L->1L
	p%2==1L->n*modpow(n,p-1)%mod
	else-> {
		val d = modpow(n,p/2)
		d*d%mod
	}
}

fun main() {
	abc000X()
}

fun abc000X() {
	val (n,k) = list()
	val a = list()

	(0 until n-k).map {i-> a[i]<a[i+k]}
			.map {if(it) "Yes" else "No"}
			.forEach(::println)
}


Measured memory_bytes: 65204
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double w = Double.parseDouble(sc.next()), h = Double.parseDouble(sc.next()), x = Double.parseDouble(sc.next()), y = Double.parseDouble(sc.next());

        System.out.println((w * h) / 2 + " " + (w / 2 == x && h / 2 == y ? "1" : "0"));
    }
}


Measured memory_bytes: 22996
function Main(input) {
  input = input.split("\n");
  var A = input[0].split(" ");
  var B = input[1].split(" ");
  var sumA = 0, sumB = 0;
  for (var i = 0; i < 4; ++i) {
    sumA += parseInt(A[i]);
    sumB += parseInt(B[i]);
  }
  console.log("%d", Math.max(sumA, sumB));
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 15456
#include <iostream>
#include <math.h>

void printRect(int w, int h) {
    for (int y=0; y<h; y++) {
        
        for (int x=0; x<w; x++) {
            if(x==0||y==0||x==w-1||y==h-1)printf("#") ;
            else printf(".");
        }
        printf("\n");
    }
    printf("\n") ;
}

int main(int argc, const char * argv[]) {
    
    while (1) {
        int h, w;
        std::cin >> h >> w ;
        if(h==0&&w==0) break ;
        printRect(w, h);
    }
    
    return 0 ;
}


Measured memory_bytes: 2984
from __future__ import print_function

import sys

import re
import array
import copy
import functools
import operator

import math
import string
import fractions
from fractions import Fraction
from fractions import gcd
# fractions.gcd() を用いること
# math.log2()はatcoderでは対応していない．留意せよ．

import collections
import itertools
import bisect

import random
import time

import heapq
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace
from queue import PriorityQueue as pq
from queue import Queue

from itertools import accumulate

from collections import deque
from collections import Counter

from operator import mul
from functools import reduce

input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return


def lcm(n, m):
    return int(n * m / gcd(n, m))


def coprimize(p, q):
    common = fractions.gcd(p, q)
    return (p // common, q // common)


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    n,m = map(int,input().strip().split())
    l=[[] for _ in range(n)]
    for _ in range(m):
        a,b = map(int,input().strip().split())
        a,b = a-1, b-1
        l[a].append(b)
        l[b].append(a)
    for i in range(n):
        print(len(l[i]))

if __name__ == '__main__':
    main()

Measured memory_bytes: 59884
#include<iostream>
int main() {
	int n,m,sum = 0,plus = 0;
	std::cin >> n;
	m = n;
	while(n) {
		plus = n % 10;
		sum = sum + plus;
		n = n / 10;
	}
	if (m%sum == 0) {
		std::cout << "Yes" << std::endl;
	}
	else {
		std::cout << "No" << std::endl;
	}
	return 0;
}

Measured memory_bytes: 256
n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))

lim = sum(a) -k
if(lim <= 0):
    print(0)
    exit()

min_ = 0
max_ = 10**12+1

a.sort()
a = tuple(a)
f.sort(reverse=True)
f = tuple(f)

for i in range(100):
    tmp = (max_ + min_)//2
    tmp_sum = 0
    for j in range(n):
        tmp_sum += max(0, a[j] - tmp//f[j])

    if(tmp_sum <= k):
        max_ = tmp
    else:
        min_ = tmp

    if(max_ - min_ == 1):
        break

print(max_)

Measured memory_bytes: 126412
#include<iostream>
#include<vector>
#include<utility>
using namespace std;

const int MAX = 1000000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
  // 前処理
  COMinit();
  int n;cin >> n;
  vector<int> a(n+1);for(int i=0;i<n+1;i++){cin >> a[i];a[i]-=1;}
  vector<bool> b(n,true);
  for(int i=0;i<n+1;i++){b[a[i]]=!b[a[i]];}
  pair<int,int> p=make_pair(-1,-1);
  for(int i=0;i<n+1;i++){
    if(b[a[i]]){
      if(p.first==-1){p.first=i;}
      else{p.second=i;break;}
    }
  }
  for(int i=1;i<=n+1;i++){
    //cout << (COM(n+1,i)-COM(n+1-(p.second-p.first+1),i-1))%MOD << endl;
    //えーーーここかよ
    int c=COM(n+1,i)-COM(p.first+(n-p.second),i-1);
    while(c<0){
      c+=MOD;
    }
    cout << c%MOD << endl;

    //cout << COM(p.first+(n-1-p.second),i-1)%MOD << endl;
  }
}


Measured memory_bytes: 25088
#include <iostream>
#include <iomanip>
#include <queue>
#include <utility>
#include <vector>
typedef long long ll;
using namespace std;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
#define repi(i, n, init) for (ll i = init; i < (n); i++)
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
vector<vector<char>> s;
vector<vector<int>> dist;
int h, w;

void bfs(queue<pair<int, int>> &q, int x, int y)
{
    repi(i, 4, 0)
    {
        int nx = x + dx[i],
            ny = y + dy[i];
        if (0 <= nx && nx < w && 0 <= ny && ny < h && s[ny][nx] != '#')
        {
            if (dist[ny][nx] > dist[y][x] + 1)
            {
                dist[ny][nx] = dist[y][x] + 1;
                q.push({nx, ny});
            }
        }
    }
}

int main()
{
    cin >> h >> w;
    s.resize(h, vector<char>(w));
    dist.resize(h, vector<int>(w, INF));
    int black = 0;
    repi(i, h, 0)
    {
        repi(j, w, 0)
        {
            cin >> s[i][j];
            if (i == 0 && j == 0 || i == h - 1 && j == w - 1)
                continue;
            if (s[i][j] == '#')
            {
                black++;
            }
        }
    }

    if (s[h - 1][w - 1] == '#')
    {
        cout << -1 << endl;
        return 0;
    }

    queue<pair<int, int>> q;

    q.push({0, 0});
    dist[0][0] = 1;
    while (!q.empty())
    {
        pair<int, int> p = q.front();
        q.pop();
        bfs(q, p.first, p.second);
    }
    if (dist[h - 1][w - 1] == INF)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << h * w - black - dist[h - 1][w - 1] << endl;
    }
    return 0;
}

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

int main()
{
    int n,m,a,b,t,tt,s;
    while(~scanf("%d%d%d%d",&n,&m,&a,&b))
    {
        if(n>m)
        {
            t=m;
        }
        else
        {
            t=n;
        }
        if(a>b)
        {
            tt=b;
        }
        else
        {
            tt=a;
        }
        printf("%d\n",tt+t);
    }
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repi(i, s, n) for (int i = (s); i < (n); i++)
#ifdef LOCAL
#define INPUT_FILE                              \
  ifstream in("atcoder-problems/abc151_c.txt"); \
  cin.rdbuf(in.rdbuf());
#define print_vec(v)                        \
  rep(l, v.size()) { cout << v[l] << " "; } \
  cout << endl;
#else
#define INPUT_FILE
#define print_vec(v)
#endif
#define CIN_OPTIMIZE \
  cin.tie(0);        \
  ios::sync_with_stdio(false);
typedef pair<int, int> P;
typedef long long ll;
typedef pair<ll, ll> pl;
const int INF = 100100100;
const ll LINF = 1e18 + 100;
const int MOD = 1e9 + 7;

int main() {
  INPUT_FILE CIN_OPTIMIZE;

  int N, M;
  cin >> N >> M;

  vector<int> ac(N, 0);
  vector<int> wc(N, 0);
  rep(i, M) {
    int p;
    string a;
    cin >> p >> a;
    p--;
    if (a == "AC") {
      ac[p] = 1;
    } else {
      if (!ac[p]) {
        wc[p]++;
      }
    }
  }

  int _ac = 0, _wc = 0;
  rep(i, N) {
    _ac += ac[i];
    if (ac[i]) {
      _wc += wc[i];
    }
  }

  printf("%d %d", _ac, _wc);
}

Measured memory_bytes: 1024
using System;

class Program {
    static void Main(string[] args) {
        string[] input = Console.ReadLine().Split(' ');
        int r = int.Parse(input[0]);
        int d = int.Parse(input[1]);
        int x = int.Parse(input[2]);
        int num;
        int resultNum;
        num = (r * x) - d;

        for (int i = 1; i <= 10; i++) {
            resultNum = num * r - d;
            Console.WriteLine(num);
            num = resultNum;
        }
    }
}

Measured memory_bytes: 11092
import java.util.*;
import java.text.*;

public class Main {

    Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        new Main().run();
    }

    void run() {

        String s = sc.next();

        int n = s.length() - 1;

        long res = 0;

        if (s.length() == 1) {
            System.out.println(s);
            return;
        }

        for (int i=0; i<(int)Math.pow(2, n); i++) {
            String bin = Integer.toBinaryString(i);

            while (bin.length() < n) bin = "0" + bin;
            bin = bin + "1";
            
            int idx = 0;
            List<Long> list = new ArrayList<>();
            for (int j=0; j<bin.length(); j++) {
                if (bin.charAt(j) == '1') {
                    list.add(Long.parseLong(s.substring(idx, j+1)));
                    idx = j+1;
                }
            }
            long tmp = 0;
            for (Long t: list) tmp += t;
            res += tmp;
        }

        System.out.println(res);

    }


}


Measured memory_bytes: 21972
#include<stdio.h>
int main(){
    char b[11];
    int cnt,max;
    max=cnt=0;
    scanf("%s",b);
    for(int i=0;i<10;i++){
        if(b[i]=='A'||b[i]=='C'||b[i]=='G'||b[i]=='T'){
            cnt++;
            if(max<cnt)max=cnt;
        }
        else{

            cnt=0;
        }
    }
    printf("%d\n",max);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<ll,pll> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int n;
vi a;

int main(){
	cin>>n;
	a=vi(n);
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		a[x-1]=i+1;
	}
	for(int i=0;i<n;i++) cout<<a[i]<<" \n"[i==n-1];
}

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


int main()
{


     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
   
  string nish;
  cin>>nish;
  long long int  dp[2020];

  for(int i=0;i<2020;i++)
  	dp[i]=0;

  dp[nish[0]-'0']=1;
  int siz=nish.size();
  long long int ans=0;

  for(int i=1;i<siz;i++)
  {
  	int temp=nish[i]-'0';
  	//cout<<temp<<endl;
  	long long int tdp[2020];
  	
  	for(int j=0;j<2020;j++)
  		tdp[j]=0;

    tdp[temp]=1;
  	for(int i1=0;i1<2019;i1++)
  	{
  		if(dp[i1]>0)
  		{
  			int total=(i1*10+temp)%2019;
  			//cout<<total<<endl;
  			if(total==0)
  		     ans+=dp[i1];
  		    tdp[total]+=dp[i1];
  		}
  	}

  	for(int i2=0;i2<2020;i2++)
  	{
  		dp[i2]=tdp[i2];
  	}
  }

  cout<<ans<<endl;


return 0;

}

Measured memory_bytes: 3740
#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef pair<ll , ll> Pair ;
const int N = 2e5 + 10 ;
Pair a[N] ;
#define f first
#define s second
ll c[N] , dp[44] ;
bool cmp(Pair a , Pair b)
{
  return a.f * (b.s + 1) >  b.f * (a.s + 1) ;
}
int main()
{
  ll n , t ;
  scanf("%lld%lld" , &n , &t) ;
  int cnt1 = 0 , cnt2 = 0 ;
  for(int i =1 ; i <= n ;i ++)
   {
     ll x , y ;
     scanf("%lld%lld" , &x , &y) ;
     if(x == 0) c[++ cnt1] = y + 1 ;
     else a[++ cnt2] = {x , y} ;
   }
   sort(a + 1 , a + cnt2 + 1 , cmp) ;
   sort(c + 1 , c + cnt1 + 1) ;
   for(int i = 0 ;i <= 30 ;i ++) dp[i] = t + 1 ;
   dp[0] = 0 ;
   for(int i = 1; i <= cnt2 ;i ++)
    for(int j = 30 ;j > 0 ;j --)
     dp[j] = min(dp[j] , (dp[j - 1] + 1) * (a[i].f + 1) + a[i].s) ;
  int ans = 0;
  for(int i = 1; i <= cnt1 ; i ++) c[i] += c[i - 1] ;
  for(int i = 0 ;i <= 30 ;i ++)
   {
     if(dp[i] > t) continue ;
     int j = 0 ;
     if(cnt1)
      j = upper_bound(c + 1 , c + cnt1 + 1 , t - dp[i]) - c - 1 ;
    ans= max(ans , j + i) ;

   }
   cout << ans << endl ;
  return 0 ;
}



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

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

int main(){
    int n;
    cin>>n;
    n%=10;
    if(n==0|n==1|n==6|n==8){
        cout<<"pon";
    }else if(n==3){
        cout<<"bon";
    }else{
        cout<<"hon";
    }


    return 0;
}

Measured memory_bytes: 3636
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
  string s;
  cin >> s;
  if(s=="zyxwvutsrqponmlkjihgfedcba"){
    cout << -1 << endl;
    return 0;
  }
  for(char c='a';c<='z';c++){
    bool flag=true;
    rep(i,s.size()){
      if(s[i]==c)flag=false;
    }
    if(flag){
      cout << s+c << endl;
      return 0;
    }
  }
  string t,r;
  int temp=0;
  for(int i=s.size();i>=1;i--){
    if(s[i]>s[i-1]){
      rep(j,i-1)cout << s[j];
      for(int j=s.size()-1;j>=i;j--){
        if(s[j]>s[i-1]){
          cout << s[j] << endl;
          return 0;
        }
      }
    }
  }
return 0;}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<functional>
#include<string>
#include<iomanip>
#include<map>
#include<utility>
#include<string>
#include<unordered_map>
#include<queue>

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

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
int gcd(int a, int b){return b ? gcd(b, a%b) : a;}
const int INF = 1000000007;

int main(){
   int n;
   cin >> n;
   vector<string> s(n);
   for(int i = 0; i < n; i++) cin >> s[i];
   sort(s.begin(), s.end());
   s.erase(unique(s.begin(), s.end()), s.end()); //uniqueはごみの先頭イテレータを返す
   cout << s.size() << endl;
   return 0;
}
 

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

public class Main {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
            int N = in.nextInt(), M = in.nextInt(), Q = in.nextInt();
            String[] S = new String[N + 1];
            char[] s0 = new char[M + 1];
            Arrays.fill(s0, '_');
            S[0] = new String(s0);
            for (int i = 1; i < N + 1; i++) {
                S[i] = "_" + in.next();
            }
//            System.out.println("S " + Arrays.toString(S));

            int[][] kuro = new int[N + 1][M + 1];
            int[][] tate = new int[N + 1][M + 1];
            int[][] yoko = new int[N + 1][M + 1];
            for (int i = 1; i < N + 1; i++) {
                int ki = 0, ti = 0, yi = 0;
                for (int j = 1; j < M + 1; j++) {
                    kuro[i][j] = kuro[i - 1][j];
                    tate[i][j] = tate[i - 1][j];
                    yoko[i][j] = yoko[i - 1][j];
                    if (S[i].charAt(j) == '1') {
                        ki += 1;
                        if (S[i - 1].charAt(j) == '1') {
                            ti += 1;
                        }
                        if (S[i].charAt(j - 1) == '1') {
                            yi += 1;
                        }
                    }
                    kuro[i][j] += ki;
                    tate[i][j] += ti;
                    yoko[i][j] += yi;
                }
            }
//            System.out.println("kuro " + Arrays.deepToString(kuro));
//            System.out.println("tate " + Arrays.deepToString(tate));
//            System.out.println("yoko " + Arrays.deepToString(yoko));

            for (int q = 0; q < Q; q++) {
                int x1 = in.nextInt(), y1 = in.nextInt(), x2 = in.nextInt(), y2 = in.nextInt();
                int cum_kuro = cum(kuro, x1, y1, x2, y2);
                int cum_tate = cum(tate, x1 + 1, y1, x2, y2);
                int cum_yoko = cum(yoko, x1, y1 + 1, x2, y2);
//                System.out.println("cums " + cum_kuro + " " + cum_tate + " " + cum_yoko);

                System.out.println(cum_kuro - cum_tate - cum_yoko);
            }
        }
    }

    private static int cum(int[][] mat, int x1, int y1, int x2, int y2) {
        x1 -= 1;
        y1 -= 1;
//        System.out.println(mat[x1][y1]);
//        System.out.println(mat[x2][y2]);
//        System.out.println(mat[x1][y2]);
//        System.out.println(mat[x2][y1]);
        return mat[x1][y1] + mat[x2][y2] - mat[x1][y2] - mat[x2][y1];
    }
}

Measured memory_bytes: 245620
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int a = input.nextInt();
        int b = input.nextInt();
        double f = (double)a / b;
        int d = (int)f;
        int r = a % b;
        System.out.println(String.format("%d %d %.5f", d, r, f));
    }
}

Measured memory_bytes: 17312
#include <bits/stdc++.h>
using namespace std;
#define ll long long int

vector<int> a(1000001);
int n;

bool pairwise() {
  // cout << "0" << endl;
  vector<int> d(1000001);
  d[1]=1;
  vector<bool> sieve(1000001,true);
  int maxa = 0;
  for(int i=0;i<n;i++) {
    maxa = max(maxa, a[i]);
    // d[a[i]] = a[i];
    // sieve[a[i]] = false;
  }
  // cout << "1" << endl;
  for(int i=2;i<=maxa;i++) {
    if(sieve[i]) {
      for(int j=i;j<=maxa;j+=i) {
        if(j) {
          d[j]=i;
          sieve[j]=false;
        }
      }
    }
  }
  // cout << "2" << endl;
  // for(int i=0;i<=maxa;i++) cout << d[i] << sieve[i]<< endl;
  unordered_set<int> div;
  for(int i=0;i<n;i++){
    int e = a[i];
    while(e!=1) {
      // cout << d[e] << endl;
      if(div.find(d[e])!=div.end()) {
        // cout << "!" << d[e] << endl;
        return false;
      }
      div.insert(d[e]);
      int f = d[e];
      // e/=d[e];
      while(e%f==0) e/=f;
    }
  }
  // cout << "3" << endl;
  return true;
}

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

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

    bool p = pairwise();
    // bool p = true;
    if(p) {
      cout << "pairwise coprime";
      return 0;
    }

    int g = a[0];
    for(int i=1;i<n;i++) g = __gcd(g,a[i]);
    if(g==1) {
      cout << "setwise coprime";
      return 0;
    }

    cout << "not coprime";

    return 0;
}

Measured memory_bytes: 14556
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,x,ans,f[400001],t[1600001];
void up(int a){
	t[a]=max(t[a*2],t[a*2+1]);
}
void turn(int a,int l,int r,int u,int v){
	if(l>u||r<u)return;
	if(l==r){
		t[a]=max(t[a],v);
		return;
	}
	int mid=(l+r)/2;
	turn(a*2,l,mid,u,v);
	turn(a*2+1,mid+1,r,u,v);
	up(a);
}
int find(int a,int l,int r,int ql,int qr){
	if(l>qr||r<ql)return 0;
	if(ql<=l&&r<=qr)return t[a];
	int mid=(l+r)/2;
	int p1=find(a*2,l,mid,ql,qr);
	int p2=find(a*2+1,mid+1,r,ql,qr);
	return max(p1,p2);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		x++;
		f[i]=find(1,1,400000,max(x-m,1),min(x+m,400000))+1;
		turn(1,1,400000,x,f[i]);
		ans=max(ans,f[i]);
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 8112
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1000000007;
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

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




Measured memory_bytes: 3580
import java.util.Scanner;
import java.lang.*;

public class Main {
	public static void main (String args[]) {
		
		Scanner scan = new Scanner(System.in);
        String str = scan.nextLine();
        
		Integer i;
        try {
        	i = Integer.parseInt(str);
        } catch (NumberFormatException nfex) {
        	System.out.println("数字を入力してください");
        	return;
        }
        
        if (1 <= i && i <= 1000000) {
        	if (i % 2 == 0) {
        		i = i / 2 - 1;
        	} else {
        		i = (i - 1) / 2;
        	}
        	System.out.println(i);
        } else {
        	System.out.println("範囲外の数字です");
        }
        return;
	}
}


Measured memory_bytes: 21844
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

// c++11
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>

#define mp make_pair
#define mt make_tuple
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

const int INF = 1 << 29;
const double EPS = 1e-9;
const ll MOD = 1000000007;

const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
string S;
map<char, int> cnt;
int N;
bool check(map<char, int> &tmp) {
  for (char i = 'a'; i <= 'c'; i++) {
    if (tmp[i] < 0) {
      return false;
    }
  }
  return true;
}
int main() {
  cin >> S;
  N = S.size();
  for (auto &val : S) {
    cnt[val]++;
  }
  // if (N == 1) {
  //   cout << "YES" << endl;
  //   return 0;
  // }
  // if (N == 2) {
  //   if (cnt[0] != cnt[1]) {
  //     cout << "YES" << endl;
  //   } else {
  //     cout << "NO" << endl;
  //   }
  //   return 0;
  // }
  vector<int> tmp;
  for (char i ='a'; i <= 'c'; i++){
      tmp.push_back(cnt[i]);
  }
  sort(tmp.begin(), tmp.end());
  if (abs(tmp[0] - tmp[2]) <= 1){
    cout << "YES" << endl;
    return 0;
  }
  cout << "NO" << endl;
  return 0;
  for (char i = 'a'; i <= 'c'; i++) {
    for (char j = 'a'; j <= 'c'; j++) {
      for (char k = 'a'; k <= 'c'; k++) {
        if (i == j or j == k or i == k) {
          continue;
        }
        map<char, int> tmp = cnt;
        int head = 0;
        bool ok = true;
        while (head < N) {
          if (head % 3 == 0) {
            tmp[i]--;
          } else if (head % 3 == 1) {
            tmp[j]--;
          } else {
            tmp[k]--;
          }
          if (not check(tmp)) {
            ok = false;
            break;
          }
          head++;
        }
        if (ok and check(tmp)) {
          cout << "YES" << endl;
          return 0;
        }
      }
    }
  }
  cout << "NO" << endl;
  return 0;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 1e3 + 5, M = 1e4 + 5, up = 1e4;
const ll LINF = 1e18 + 5;
int n;
struct node
{
	int w, s, v;
	bool operator < (const node& x) { return w + s > x.w + x.s; }
}p[N];
ll dp[N][M];
int main()
{
 	ios::sync_with_stdio(false);
 	cin.tie(0);
 	cin >> n;
 	for(int i=1; i<=n; i++)
 		cin >> p[i].w >> p[i].s >> p[i].v;
 	sort(p+1, p+n+1);
 	for(int i=1; i<=n; i++)
 	{
 		for(int j=0; j<=up; j++)
 		{
 			dp[i][j] = dp[i-1][j];
 			if(j>=p[i].w) dp[i][min(p[i].s, j-p[i].w)] = max(dp[i][min(p[i].s, j-p[i].w)], dp[i][j]+p[i].v);
 		}
 		dp[i][p[i].s] = max(dp[i][p[i].s], (ll)p[i].v);
 	}
 	ll ans = 0;
 	for(int i=0; i<=up; i++) ans = max(ans, dp[n][i]);
 	cout << ans;
	return 0;
}


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

using ll = long long;
template <typename T> constexpr T inf = numeric_limits<T>::has_infinity ? numeric_limits<T>::infinity() : numeric_limits<T>::max() / 4;

#define REP(i, stop) FOR(i, 0, stop)
#define FOR(i, start, stop) for (ll i = start, i##_len = stop; i < i##_len; ++i)
#define RREP(i, n) for (ll i = n; i-- > 0;)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define COMP(key) [](const auto& a, const auto& b) { return a.key < b.key; }

template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& a) { return is >> a.first >> a.second; }
template<typename T> istream& operator>>(istream& is, vector<T>& a) { for (T& x : a) is >> x; return is; }

template<typename T> using pop_max = std::priority_queue<T>;
template<typename T> using pop_min = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template<typename T> void LOG(const T& x) { cerr << x << "\n"; }
template<typename T> void LOG(const vector<T>& a) { for (const T& x : a) cerr << x << " "; cerr << "\n"; }
template<typename T> void LOG(const vector<vector<T>>& a) { for (const auto& x : a) LOG(x); }
template<typename T, std::size_t S> void LOG(const T (&a)[S]) { REP(i, S) cerr << a[i] << " "; cerr << "\n"; }
template<typename T, std::size_t S, std::size_t R> void LOG(const T (&a)[S][R]) { REP(i, S) { REP(j, R) cerr << a[i][j] << " "; cerr << "\n"; } }

ll ceil(ll a, ll b) { return a > 0 ? (a - 1) / b + 1 : a / b; }
ll gcd(ll a, ll b) { while (b != 0) { ll t = b; b = a % b; a = t; } return a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll gcd(const vector<ll>& v) { return accumulate(v.begin(), v.end(), 1LL, static_cast<ll(*)(ll, ll)>(gcd)); }
ll lcm(const vector<ll>& v) { return v.empty() ? 0LL : accumulate(v.begin() + 1, v.end(), v[0], static_cast<ll(*)(ll, ll)>(lcm)); }
ll pow(ll x, ll y, ll z) { ll a = 1; while (y > 0) { if (y & 1) a = a * x % z; x = x * x % z; y /= 2; } return a; }
ll inv(ll x, ll m) { return pow(x, m - 2, m); }

template<typename T> bool chmax(T& x, const T& y) { return x < y ? x = y, true : false; }
template<typename T> bool chmin(T& x, const T& y) { return x > y ? x = y, true : false; }

struct InitCpp { InitCpp() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); } } init_cpp;

const ll INF = inf<ll>;
using P = pair<ll, ll>;
const ll M = 1000000007;
signed main() {
  ll n,k;
  cin>>n>>k;
  vector<ll> p(n);
  cin>>p;
  vector<double> sum(n+1);
  REP(i,n){
    sum[i+1]=sum[i]+(1+(double)p[i])/2;
  }
  // LOG(sum);
  double ans=0;
  for(ll i=0;i<n-k+1;i++){
    chmax(ans,sum[i+k]-sum[i]);
    // LOG(sum[i+k]-sum[i]);
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 3456
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
n=int(input())
a={}
for i in range(0,n):
  s=input()
  if s in a.keys():
    a[s]=a[s]+1
  else:
    a[s]=1
m=int(input())
for i in range(0,m):
  t=input()
  if t in a.keys():
    a[t]=a[t]-1
r=0
for k in a.keys():
  r=max(r,a[k])
print(r)




Measured memory_bytes: 3064
a,b,c = map(int,input().split())
if a%2 == 1 or b%2 == 1 or c%2== 1 :
    print(0)
    exit()
elif a == b and b == c :
    print(-1)
    exit()
count = 0
while (a%2 == 0 and b%2 == 0 and c%2 == 0) :
    count += 1
    x = (a+b)/2
    y = (b+c)/2
    z = (c+a)/2
    a = x
    b = y
    c = z


print(count)

Measured memory_bytes: 9268
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
 
int main() {
  ll n;
  cin>>n;
  vector<int> ab(n+1);
  vin x(n+1);
  map<int,int> y;
  rep(i,0,n){
   // int ab;
    cin>>ab[i+1];
    //a[i+1]=make_pair(i+1,ab);//1 index
    x[i+1]=i+1+ab[i+1];
    y[i+1-ab[i+1]]++;
  }
  
  
  //////////
  ll ans=0;
  
  rep(i,1,n+1){
    if(y[x[i]]>0){
     y[x[i]-2*ab[i]]--;
      ans+=y[x[i]];
     // cout<<x[i]<<endl;
    }
   // cout<<x[i]<<endl;
  }
  
  
  
  
  
  
  
  
  
  
  
  cout<<ans<<endl;
}

Measured memory_bytes: 21780
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
using ll=int64_t;
#define A(a) (a).begin(),(a).end()
#define mp make_pair
ll MOD=1e9+7;
ll N,M,X,Y,Z,y,z,K;
vector<ll> p,m;
ll r(ll X){
    if(p[X]==X) return X;
    return p[X]=r(p[X]);    
}
void u(ll X,ll Y){
    X=r(X);
    Y=r(Y);
    if(X!=Y)p[X]=Y;
}
ll mo(ll a,ll n){
    ll r=1;
    while(n){
        if(n&1)r=r*a%MOD;
        a=a*a%MOD;
        n/=2;
    }
    return r;
}
int main(){
    cin>>N>>M>>K;
    p.resize(N);
    m.resize(M);
    vector<tuple<ll,ll,ll>> e(M);
    rep(i,M){
      	cin>>X>>Y>>Z;X--,Y--;
        e[i]=make_tuple(Z,X,Y);
    }
    sort(A(e));
    rep(i,M){
      	tie(m[i],y,z)=e[i];
        rep(i,N)p[i]=i;
        u(z,y);
        rep(j,M){
          	tie(Z,X,Y)=e[j],m[i]+=(r(X)!=r(Y))*Z,u(X,Y);
        }
    }
    sort(A(m));
    ll a=0;
    rep(i,M)if(i&&m[i]==K)a+=mo(2,M-i);
    cout<<a%MOD;
}


Measured memory_bytes: 3708
#include <stdio.h>

int
main(int argc, char *argv[])
{
  int r, g, b, n, x, y, cnt = 0;
  scanf("%d %d %d %d", &r, &g, &b, &n);
  
  for(x = 0; x <= n / r; x++){
    for(y = 0; y <= (n - r * x) / g; y++){
      if((n - r * x - g * y) % b == 0) cnt++;
    }
  }
  
  printf("%d\n", cnt);
  
  return 0;
}

Measured memory_bytes: 128
using System;

    class MainClass
    {
        public static void Main(string[] args)
        {
            int cnt = 0;
            int num =int.Parse(Console.ReadLine());
            string[] input = Console.ReadLine().Split(' ');
            for (int i = 1; i < num;i++)
            {
                if(int.Parse(input[i]) == int.Parse(input[i-1]))
                {
                    cnt++;
                    i++;
                }
            }
            Console.WriteLine(cnt);

        }
    }


Measured memory_bytes: 11092
#include<iostream>
#include<cstdio>
using namespace std;
const int N=55;
int n; 
string s[N];
string t;
int a[N];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>s[i]>>a[i];
	cin>>t;
	int ans=0;
	for(int i=1;i<=n;i++)
		if(s[i]==t)
		{
			for(int j=i+1;j<=n;j++)
				ans+=a[j];
			printf("%d",ans);
			return 0;
		}
	return 0;
}

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

int main() {
  int a, b;
  cin >> a >> b;
  
  a *= b;
  a %= 2;
  if (!a) {
    cout << "Even" << endl;
  } else {
    cout << "Odd" << endl;
  }
  
}

Measured memory_bytes: 256
using System.Collections;
using System;
using System.Collections.Generic;

public class Sample4{

	public static void Main(){

		string line;
		List <string> stringList = new List<string> ();

		do {

			line = Console.ReadLine ();

			if (line == null || !canDo(line)){
				break;
			}
			stringList.Add (line);

		} while (line != null);


		foreach (var s in stringList) {

			string[] tempStr = s.Split (' ');

			double x = getX (int.Parse (tempStr [0]),
				int.Parse (tempStr [1]),
				int.Parse (tempStr [2]),
				int.Parse (tempStr [3]),
				int.Parse (tempStr [4]),
				int.Parse (tempStr [5]));

			double y = getY (int.Parse(tempStr[0]),
				int.Parse(tempStr[1]),
				int.Parse(tempStr[2]),
				x);

			Console.WriteLine ("{0:f3} {1:f3}",x,y);
		}

	}

	public static double getX(int a, int b, int c, int d, int e, int f){

        double value1 = c*e - b*f;
        double value2 = a*e - d*b;
        
		double x = value1/value2;


		return Math.Round(x, 3, MidpointRounding.AwayFromZero);;
	}

	public static double getY (int a, int b, int c, double x){


		double y = (c - a * x) / b;
		return Math.Round(y, 3, MidpointRounding.AwayFromZero);;
	}

	public static bool canDo (string line){

		string[] tempStr = line.Split (' ');

			foreach (var t in tempStr) {

			if (int.Parse (t) < -1000 || int.Parse (t) > 1000) {
					return false;
				}

			}
		return true;
	}
}

Measured memory_bytes: 5776
N=int(input())
A=[0 for i in range(N)]
A=input().split()
for i in range(N):
    A[i]=(int)(A[i])
for i in range(N):
    v=A[i]
    j = i-1
    while j>=0 and A[j]>v:
        A[j+1]=A[j]
        j=j-1
        A[j+1]=v
    for k in range(N):
        if k<N-1:
            print(A[k],end=" ")
        if k==N-1:
            print(A[k])



Measured memory_bytes: 5980
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;

const int maxn = 12345;
ll n , a[maxn];

ll calc(ll x)
{
	ll ret = 0;
	for(int i=0;i<n;i++) ret += abs(a[i] - x) * abs(a[i] - x);
	return ret;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	cin >> n;
	ll mn = 1e17;
	for(int i=0;i<n;i++) cin >> a[i];
	for(int i=-100;i<=100;i++)
	{
		ll x = calc(i);
		if(x < mn)
		{
			mn = x;
		}
	}
	cout << mn << endl;
}	

Measured memory_bytes: 256
# coding: utf-8

# https://atcoder.jp/contests/abc117


def main():
    N = int(input())
    L = list(map(int, input().split()))

    L = sorted(L, reverse=True)

    if L[0] < sum(L[1:]):
        return "Yes"
    else:
        return "No"


print(main())


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

#define ll long long
#define INF 99999999
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

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

    if( N > 10 ) cout << R << endl;
    else cout << R + 100 * (10 - N) << endl;
}


Measured memory_bytes: 256
import math

n,k=map(int,input().split())
ans=0
cnt=0
a=n
while n>0:
    if n>=k:
        ans+=(n-k+1)/a*(1/2)**cnt
        n=k-1
    k=math.ceil(k/2)
    cnt+=1
    #print(n,k,ans)
print(ans)

Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cstdio>
#include<string>
#include<vector>
//#include<string>
//#include<sstream>
using namespace std;

int main(){
	long long n,m,i,min,num;
	scanf("%lld%lld",&n,&m);
	num=m-n*2;
	if(num>0){
		printf("%lld\n",n+num/4);
	}
	else if(num<0){
		num=abs(num);
		printf("%lld\n",m/2);
	}
	else{
		printf("%lld\n",n);
	}
	//printf("%lld\n",num/4);
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
n,k = [int(i) for i in readline().split()]

l = [n]

n %= k
l.append(n)

while True:
    diff = abs(l[-1]-k)
    if diff not in l:
        l.append(diff)
    else:
        break

print(min(l))

Measured memory_bytes: 3060
//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
//assert(q==w) если q!=w --> runtime error
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define ub upper_bound
#define lb lower_bound
#define bit __builtin_popcount
#define memset(x) memset(x,0,sizeof(x))

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<vector<int>> matrix;

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

const ll maxn=2e5+123;
const ll inf=1e9+123;
const ll linf=1e18+123;
const ll mod=1e9+7;
const double eps=1e-9;
const double pi=acos(-1);
int dx[8]={0,1,-1,0,1,-1,1,-1};
int dy[8]={1,0,0,-1,1,1,-1,-1};
int a[maxn],color[10];
int main(){
    boost();
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    ll ans=1;
    for(int i=1;i<=n;i++){
        int cntr=0,id=0;
        if(color[1]==a[i]){
            cntr++;
            id=1;
        }
        if(color[2]==a[i]){
            cntr++;
            id=2;
        }
        if(color[3]==a[i]){
            cntr++;
            id=3;
        }
        ans*=cntr;
        ans%=mod;
        color[id]++;

    }
    cout<<ans;
	exit(0);
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
using namespace std;
typedef long long int ll;

int cnt[6]={};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n; cin >> n;
    for(int i=0;i<n;i++){
        double h; cin >> h;
        if(h<165)cnt[0]++;
        else if(h<170)cnt[1]++;
        else if(h<175)cnt[2]++;
        else if(h<180)cnt[3]++;
        else if(h<185)cnt[4]++;
        else cnt[5]++;
    }
    for(int i=1;i<=6;i++){
        printf("%d:",i);
        for(int j=0;j<cnt[i-1];j++){
            printf("*");
        }
        printf("\n");
    }
}



Measured memory_bytes: 3240
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<set>
#include<stdio.h>
#include<ctype.h>
using namespace std;
int main()
{
	string s;
	cin >> s;
	int x = s.size();
	string ss = s;
	reverse(s.begin(), s.end());
	int f = 0;
	for (int i = 0; i < x; i++)
	{
		if (s.at(i) != ss.at(i))
		{
			f++;
		}
	}
	cout << f / 2 << endl;
	
}


Measured memory_bytes: 256
import java.util.*;
public class Main
{
	public static void main(String[] args) 
	{
		Scanner in=new Scanner(System.in);
		while(in.hasNext())
		{
			int D=in.nextInt();
			int N=in.nextInt();
			int T[]=new int[D];
			int A[]=new int[N];
			int B[]=new int[N];
			int C[]=new int[N];
			int dp[][]=new int[D][N];//D日にNを着た時の最大値
			int clo[][]=new int[D][N];//Dの日にNの服を着ることができるか
			int ans=0;
			for(int i=0;i<D;i++)//i日の気温
				T[i]=in.nextInt();
			for(int i=0;i<N;i++)
			{
				A[i]=in.nextInt();
				B[i]=in.nextInt();
				C[i]=in.nextInt();
			}
			for(int i=0;i<D;i++)
				for(int j=0;j<N;j++)
				{
					dp[i][j]=-1;
					if(A[j]<=T[i]&&T[i]<=B[j])//着れる
						clo[i][j]=1;
				}
			for(int i=0;i<N;i++)
				if(clo[0][i]==1)
					dp[0][i]=0;

			for(int i=0;i<D-1;i++)  //i日に jの服 kの服
				for(int j=0;j<N;j++)
				{
					if(dp[i][j]>=0)
						for(int k=0;k<N;k++)
						{
							if(clo[i+1][k]==1)
								dp[i+1][k]=Math.max(dp[i+1][k], dp[i][j]+Math.abs(C[j]-C[k]));
							
							if(i+2==D)
								ans=Math.max(ans,dp[i+1][k]);
						}
				}
			System.out.println(ans);
		}
	}

	static public void debug(Object... o)
	{
		System.out.println(Arrays.deepToString(o));
	}
}

Measured memory_bytes: 24920
#include <bits/stdc++.h>
#include<cmath>
#define N 100005
#define A 1000005
#define MOD 1000000007 // //100000000 998244353 //
#define inf 1000000000000000000
#define ll long long
//#define M_PI 3.141592653589793238463

using namespace std;

#define pii pair<ll, ll>
#define piii pair<ll, pii>
#define ft first
#define sd second
#define pb push_back
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n-1; i >= 0; i--)
#define itr(it, x) for(auto it = x.begin(); it != x.end(); it++)
#define mem(a, b) memset(a, (ll)b, sizeof(a))
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define edge(v, x, y) v[x].pb(y); v[y].pb(x);
#define popcount __builtin_popcount
#define ANS(s) {cout << s << "\n"; return;}

//~~~~~~fancy print~~~~~~~//
#define printpii(a) cout << a.ft << " " << a.sd << endl;
#define printpiii(a) cout << a.ft << " " << a.sd.ft << " " << a.sd.sd << endl;
#define print(a, n) rep(i, n) cout << a[i] << " "; cout << endl;
#define printv(v) for(auto x: v)cout << x << " "; cout << endl;
#define printm(a, n, m) rep(i, n) { rep(j, m) cout << a[i][j] << "\t"; cout << endl;}

ll lx[4] = {0, 0, 1, -1};
ll ly[4] = {1, -1, 0, 0};
ll dx[8] = {0, 0, 1, -1, 1, -1, 1, -1};
ll dy[8] = {1, -1, 0, 0, 1, 1, -1, -1};
void fast(){ios_base::sync_with_stdio(false);cin.tie(0);cout << setprecision(12) << fixed;}

void solve(){
    ll n, k, a = 0;
    cin >> n >> k;
    map<ll ,ll> mp;
    rep(i, n)
    {
        ll x; cin >> x; mp[x]++;
    }
    vector<ll> v;
    itr(it, mp) v.pb({it->sd});
    sort(allr(v)); //printv(v);
    for(ll i = k; i < v.size(); i++) a += v[i];
    cout << a;
}

int main(){
    /*#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif*/
    fast();
    ll t = 1; //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}



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

int main(){
  
  //入力
  int H; int W;
  cin >> H >> W;
  char Maze[H][W+1];
  for(int i=0;i<H;i++){
    string S;
    cin >> S;
    for(int j=0;j<W;j++){
      Maze[i][j]=S[j];
    }
    Maze[i][W]='\0';
  }
  
  //道があるかどうかを入力
  int Dist[H*W][H*W];
  for(int i=0;i<H*W;i++){
    for(int j=0;j<H*W;j++){
      if(i!=j)Dist[i][j]=INF;
      else Dist[i][j]=0;
    }
  }
  
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(Maze[i][j]=='#') continue;
      if(i!=H-1){
        if(Maze[i+1][j]=='.'){
          Dist[i*W+j][(i+1)*W+j]=1;
          Dist[(i+1)*W+j][i*W+j]=1;
        }
      }
      if(j!=W-1){
        if(Maze[i][j+1]=='.'){
          Dist[i*W+j][i*W+(j+1)]=1;
          Dist[i*W+(j+1)][i*W+j]=1;
        }
      }
    }
  }
  
  
  //ワーシャル・フロイド法
  for(int k=0;k<H*W;k++){
    for(int i=0;i<H*W;i++){
        for(int j=0;j<H*W;j++)Dist[i][j]=min(Dist[i][j],Dist[i][k]+Dist[k][j]);
    }
  }
  
  
  //最大値を出力
  int N = H*H*W*W;
  vector<int> DisL;
  for(int i=0;i<N;i++){
    if(Dist[i/(W*H)][i%(W*H)] != INF){
      DisL.push_back(Dist[i/(W*H)][i%(W*H)]);
    }
  }
  sort(DisL.begin(), DisL.end(),greater<int>());
  cout << DisL.at(0) << endl;
  
}

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

int main(){
    using namespace std;
    unsigned long Q;
    cin >> Q;
    constexpr auto M{205891132094649UL};
    const auto& calc = [](auto a, auto b, auto c, auto d){
        auto u{b}, p{M};
        while(p /= 3)if((a / p + (4 - a / p % 3) % 3) * p <= c && b / p % 3 == 1){
            u = b / (3 * p) * 3 * p + 2 * p;
            break;
        }
        return c - a + min(u - b + max(u, d) - min(u, d), b + d - 2 * (b / (3 * p) * 3 * p + p - 1));
    };
    for(unsigned long _{0}, a, b, c, d; _ < Q; ++_){
        cin >> a >> b >> c >> d;
        if(--a > --c)swap(a, c), swap(b, d);
        if(--b > --d){
            b = M - b - 1;
            d = M - d - 1;
        }
        cout << max(calc(a, b, c, d), calc(b, a, d, c)) << endl;
    }
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>

#define REP(i,a) for(int i = 0;i < (a);++i)
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SIZE(obj) (int)(obj).size()
#define MAX(list) std::max(list)
#define MIN(list) std::min(list)

using ll = long long;
using namespace std;

int main() {
    int N; cin >> N;
    vector<ll> num(N);
    REP(i, N)cin >> num[i];

    sort(num.begin(), num.end(), [](ll a, ll b) {return a > b; });

    map<ll, int> dic;
    for (auto&& item : num) {
        dic[item]++;
    }

    ll ans = 0;
    for (auto&& item : num) {
        if (dic[item] == 0)continue;
        dic[item]--;
        ll T = 1;
        while (T <= item) {
            T *= 2;
        }
        ll B = T - item;
        if (dic[B] >0) {
            dic[B]--;
            ans++;
        }
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 26752
import numpy as np

n = int(input())

array = np.zeros(n, dtype = np.int)

for i in range(n):
    array[i] = input()

next_number = array[0]
counter = 1

for i in range(n):
    if next_number == 2:
        print(counter)
        break
    else:
        next_number = array[next_number-1]
        counter += 1
        if i == n-1:
            print(-1)
    

Measured memory_bytes: 14412
#include "iostream"
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#include <math.h>
#include <cctype>
#include <stack>
#include <vector>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <iomanip>
using namespace std;
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007

ll a,b,c,x,y,ans;
int main(int argc, char const *argv[]) {
  std::cin >> a >> b >> c >> x >> y;
  if(a+b<c*2){
    std::cout << x*a+b*y << '\n';
    return 0;
  }
  else{
    ans=min(x,y)*2*c;
    if(x>y) ans+=min(a,2*c)*(x-y);
    else ans+=min(b,c*2)*(y-x);
    std::cout << ans << '\n';
  }
      
  return 0;
}


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

int main()
{ 
  std::string s, t ;
  cin >> s >> t ;
  vector<std::string> data ;
  std::string search = s + s ;

  for(int i = 0 ; i < s.size() ; i++)
  {
    string str ;
    for(int j = i ; j < s.size() + i ; j++)
    { 
      str += search.at(j) ;
    }
    data.push_back(str) ;
  } 

  auto answer = find(data.begin(), data.end(), t) ;
  if( answer != data.end() )
  {
    cout << "Yes" << endl ;
  }
  else
  {
    cout << "No" << endl ;
  }
  
}


Measured memory_bytes: 256