akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define irep(i,a,b) for(ll i=ll(a);i>=ll(b);i--)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define pb push_back
#define mp make_pair
#define F .first
#define S .second 
using ll=long long;
using ld=long double;
const ll INF = 1LL<<60;
const ll mod=1e9+7;
using namespace std;
ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }

int main(){
    ll a,b,n,ans=0;
    cin>>a>>b>>n;
    ll c=GCD(a,b);
    ll d=n*c/(GCD(n,c));
    rep(i,max((ll)0,d-a),min(n,d+a)+1)ans=max(ans,(a*i)/b-a*(i/b));
    //rep(i,0,min(n,b))ans=max(ans,(a*i)/b-a*(i/b));
    ll aa=min((ll)n,b-1);
    ll bb=max((ll)0,b-10000000);
    irep(i,aa,bb)ans=max(ans,(a*i)/b-a*(i/b));
    cout<<ans;
}



Measured memory_bytes: 3628
from collections import Counter


def solve(string):
    n, *ss = string.split()
    d = Counter(s for s in map(lambda x: "".join(sorted(x)), ss))
    return str(sum([v * (v - 1) // 2 for v in d.values()]))


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(n)])))


Measured memory_bytes: 27852
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
import numpy as np
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    a, b, c = LI()
    if a + b >= c:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    return

#C
def C():
    n = II()
    ab = LIR(n)
    cd = LIR(n)
    ab.sort()
    cd.sort()
    check = [0 for i in range(n)]
    ans = 0
    #print(ab)
    for _, c in enumerate(cd):
        d = c[1]
        c = c[0]
        maxy = -1
        x = -1
        for k, a in enumerate(ab):
            b = a[1]
            a = a[0]
            if maxy < b and c > a and check[k] == 0 and d > b:
                maxy = b
                x = k
                #print(a,b,c,d)
        if x != -1:
            ans += 1
            check[x] += 1
    print(ans)


    return

#D
def D():
    N = II()
    a = LI()
    b = LI()
    ans = 0
    for i in range(29):
        t = 2 ** i
        a2 = [A % (2 * t) for A in a]
        b2 = [B % (2 * t) for B in b]
        a2.sort()
        b2.sort()
        ansb = 0
        for A in a2:
            ansb += np.searchsorted(b2, 2 * t - A) - np.searchsorted(b2, t - A)
            ansb += N - np.searchsorted(b2, 3* t - A)
            #print(ansb)
        #ans += (ansb % 2) << i
        ans += ((ansb %2 ) << i)
    print(ans)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    A()


Measured memory_bytes: 13892
#include <stdio.h>
 
using namespace std;
 
struct Node{
    Node(){
        left_child = right_child = parent = -1;
    };
    int left_child,right_child,parent;
};
 
void preORDER(Node order[],int id){
    printf(" %d",id);
    if(order[id].left_child != -1) preORDER(order,order[id].left_child );
    if(order[id].right_child != -1) preORDER(order,order[id].right_child );
}
 
void inORDER(Node order[],int id){
    if(order[id].left_child != -1) inORDER(order,order[id].left_child );
    printf(" %d",id);
    if(order[id].right_child != -1) inORDER(order,order[id].right_child );
}
 
void postORDER(Node order[],int id){
    if(order[id].left_child != -1) postORDER(order,order[id].left_child );
    if(order[id].right_child != -1) postORDER(order,order[id].right_child );
    printf(" %d",id);
}
 
int main(){
    int n,id,left,right,root_id;
    scanf("%d",&n);
    Node order[n];
    for(int i = 0; i < n; i++){
        scanf("%d %d %d",&id,&left,&right);
        if(left != -1){
            order[id].left_child = left;
            order[left].parent = id;
        }
        if(right != -1){
            order[id].right_child = right;
            order[right].parent = id;
        }
    }
 
    for(root_id = 0; root_id < n; root_id++){
        if(order[root_id].parent == -1) break;
    }
 
    printf("Preorder\n");
    preORDER(order,root_id);
    printf("\n");
 
    printf("Inorder\n");
    inORDER(order,root_id);
    printf("\n");
 
    printf("Postorder\n");
    postORDER(order,root_id);
    printf("\n");
}


Measured memory_bytes: 2724
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

char ch[100010];

int main() {
    int n;
    scanf("%s", ch + 1);
    n = strlen(ch + 1);
    for(int i = 1; i <= n; i++) ch[i] -= '0';
    if(ch[1] == 0 || ch[n] == 1) {
        puts("-1");
        return 0;
    }
    for(int i = 1; i < n - 1; i++)
        if(ch[i] ^ ch[n - i]) {
            puts("-1");
            return 0;
        }
    vector <int> V;
    V.clear();
    for(int i = 1; i <= n; i++) if(ch[i] == 1) V.push_back(i);
    V.push_back(n);
    int cnt = 1, nw = 1;
    for(int i = 0; i + 1 < V.size(); i++) {
        printf("%d %d\n", cnt + 1, nw);
        nw = ++cnt;
        for(int j = V[i]; j < V[i + 1] - 1; j++) printf("%d %d\n", nw, ++cnt);
    }
    return 0;
}

Measured memory_bytes: 2040
import java.util.Scanner;

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

		double r = sc.nextDouble();
		double are = 0;
		double circ = 0;

		are = r * r * Math.PI;
		circ = (r + r) * Math.PI;
				;
		System.out.printf("%f %f\n", are, circ);

	}
}

Measured memory_bytes: 28264
#include<bits/stdc++.h>
using namespace std;
int main(){
long long A,B,K;
  cin>>A>>B>>K;
  if(A>=K){
  cout<<A-K<<" "<<B<<endl;
  }
  else if((A+B)>=K){
  
  cout<<0<<" "<<B-(K-A)<<endl;
  }
  else{
  cout<<0<<" "<<0<<endl;
  }

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll K = 1E9 + 7.1;
ll extended_euclid(ll a, ll b, ll &x, ll &y) {
	ll xx = y = 0;
	ll yy = x = 1;
	while (b) {
		ll q = a / b;
		ll t = b; b = a%b; a = t;
		t = xx; xx = x - q*xx; x = t;
		t = yy; yy = y - q*yy; y = t;
	}
	return a;
}
ll mod_inverse(ll a, ll n) {
	ll x, y;
	ll g = extended_euclid(a, n, x, y);
	if (g > 1) return -1;
	return (x + n) % n;
}
ll perm_mod(ll n, ll k, const ll m)
{
    assert(m > 0);
    if (k > n) return 0;
    ll ret = 1;
    while (k--)
    {
        ret = (ret * (n--) % m) % m;
    }
    return ret;
}
ll n;
ll a[100005];
ll fact[100005];
ll choose1[100005];
ll choose2[100005];

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    unordered_map<ll, ll> mt; // val -> posß
    for (ll i = 0; i <= n; ++i)
        cin >> a[i];
    ll p1 = -1;
    ll p2 = -1;
    for (ll i = 0; i <= n; ++i)
    {
        if (p2 == -1) {
            if (mt.count(a[i])) {
                p1 = mt[a[i]];
                p2 = i;
            } else mt[a[i]] = i;
        }
    }
    fact[0] = 1;
    choose1[0] = 1;
    choose2[0] = 1;
    for(ll i = 1; i <= n + 1; i++) {
        choose1[i] = (((choose1[i - 1] * (n + 1 - i + 1)) % K) * mod_inverse(i, K)) % K;
        choose1[i] %= K;
    }
    for(ll i = 1; i <= n + 1; i++) {
        fact[i] = (fact[i - 1] * i) % K;
    }
    for(ll i = 1; i <= p1 + n - p2; i++) {
        choose2[i] = (((choose2[i - 1] * (p1 + n - p2 - i + 1)) % K) * mod_inverse(i, K)) % K;
        choose2[i] %= K;
    }

    // cout << p1 <<  ' ' << p2 << endl;
    for(ll i = 1; i <= n + 1; ++i) {
        ll r = choose1[i];
        r %= K;
        
        r -= choose2[i - 1];
        r %= K;
        r += K;
        r %= K;
        cout << r << '\n';
    }
}

Measured memory_bytes: 7716
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename Q_temp>
using smaller_queue = priority_queue <Q_temp, vector<Q_temp>, greater<Q_temp> >;

const int INF = (int) 1e9;
const ll LINF = (ll) 4e18;
const ll MOD = (ll) (1e9 + 7);
const double PI = acos(-1.0);
const int limit = 100010;

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbg2(x_) for(auto a_ : x_) cerr << a_ << " "; cerr << endl;
#define dbg3(x_ , sx_) rep(i, sx_) cerr << x_[i] << " "; cerr << endl;
vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

inline ll CEIL(ll a, ll b) {
    return (a + b - 1) / b;
}

//------------------------------------------------------
#define int ll
const int MAX_N = 1 << 17; //100000ぐらい

class SegmentTree {
public:
    int N; //要素数
    vector<ll> dat;

    SegmentTree(int n_) {
        N = 1;
        while (N < n_) N *= 2;
        dat.assign(2 * N - 1, -1);
    }

    void update(int k, int a) { //k番目(0-indexed)をaに変更
        k += N - 1; //一番下
        dat[k] = a;
        while (k > 0) {
            k = (k - 1) / 2; //1つ上がる
            //更新
            if (dat[k * 2 + 1] == -1) dat[k] = dat[k * 2 + 2];
            else if (dat[k * 2 + 2] == -1) dat[k] = dat[k * 2 + 1];
            else dat[k] = __gcd(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }

    //[a, b)の値（最小値/和/etc.）を求める
    //kは節点の番号、l, rはその節点が[l,r)に対応づいていることを表す
    //外からはquery(a, b, 0, 0, N)と呼ぶ

    int query(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (a == b) return -1;
        if (r < 0) r = N;
        if (r <= a || b <= l) return -1;
        //[a, b)が[l,r)を完全に含む
        if (a <= l && r <= b) return dat[k];
        else {
            int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
            int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
            if (vl == -1) return vr;
            else if (vr == -1) return vl;
            else return __gcd(vl, vr);
        }
    }
};

main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int a[n];
    rep(i, n) cin >> a[i];
    SegmentTree sg(n);
    rep(i, n) sg.update(i, a[i]);
    int ans = 1;

    rep(i, n) {
        int l = sg.query(0, i, 0, 0, sg.N);
        int r = sg.query(i + 1, n, 0, 0, sg.N);
        if (l == -1) ans = max(ans, r);
        else if (r == -1) ans = max(ans, l);
        else ans = max(ans, __gcd(l, r));
        cerr << l << endl;
        cerr << r << endl;
    }
    cout << ans << endl;
    rep(i, 3) cerr << sg.dat[i] << endl;

    return 0;
}



Measured memory_bytes: 3072
import math

n = int(input())
xy_list = [list(map(int,input().split())) 
           for nesya in range(n)]
c = 0
for xy in xy_list:
  x = xy[0]
  y = xy[1]
  for ab in xy_list:
    a = ab[0]
    b = ab[1]
    c += math.sqrt((x-a)**2+(y-b)**2)
print(c/n)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

vi Bin(ll N){
    int digit = 40;
    vi bin(digit,0);
    ll bb=1;
    for(int i=0;i<digit;i++){
        if((N%(bb*2))/bb==1) bin[i]++;
        bb *= 2;
    }
    return bin;
}
vi XORFactorial(ll N){
    int digit = 40;
    vi bin(digit,0);
    ll n = N%4;
    if(n==3) return bin;
    if(n==0) return Bin(N);
    if(n==1){
        bin[0] = 1;
        return bin;
    }
    else{
        bin = Bin(N);
        if(bin[0]==1) bin[0]=0; else bin[0]=1;
        return bin;
    }
}
int Main(){
    ll A, B, ans=0, bb=1;
    cin >> A >> B;
    vi XA,XB;
    XB = XORFactorial(B);
    if(A==0){
        for(int i=0;i<40;i++){
            if(XB[i]==1) ans += bb;
            bb *= 2;
        }
        cout << ans << endl;
        return 0;
    }
    XA = XORFactorial(A-1);
    for(int i=0;i<40;i++){
        if(XA[i]!=XB[i]) ans += bb;
        bb *= 2;
    }
    cout << ans << endl;
}

int main(){ios::sync_with_stdio(false);Main();return 0;}

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

#define speed ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define test ll t; cin>>t; while(t--)
#define ll int
#define endl "\n"
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define PI 3.1415926535897932384626
#define inf 1e18
#define vll vector<ll>
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define fl(i,a,b) for(ll i=a;i<b;i++)
#define flr(i,a,b) for(ll i=a;i>b;i--)
#define print(v) for(auto i=v.begin();i!=v.end();i++){cout<<*i<<" ";}cout<<"\n";
#define MOD 1000000007
const ll N = 2e5;
map<ll,ll> mp;

int main()
{
    speed;
   	ll n,x,y; cin>>n>>x>>y;
   	--x;--y;
   	forn(i,n){
   		for(ll j=i+1;j<n;++j){
   			ll val = min(abs(j-i),min(abs(x-i)+1+abs(j-y),abs(y-i)+1+(j-x)));
   			++mp[val];
   		}
   	}
   	fl(i,1,n){
   		cout<<mp[i]<<endl;
   	}
    return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
long mod=1e9+7;
int N,M,S[2];
vector<pair<int,int> >G[1<<17];
int U[2<<17],V[2<<17],D[2<<17];
long d[2][1<<17],w[2][1<<17];
main()
{
	cin>>N>>M>>S[0]>>S[1];
	for(int i=0;i<M;i++)
	{
		cin>>U[i]>>V[i]>>D[i];
		G[U[i]].push_back(make_pair(V[i],D[i]));
		G[V[i]].push_back(make_pair(U[i],D[i]));
	}
	for(int _=0;_<2;_++)
	{
		for(int i=0;i++<N;)d[_][i]=1e18;
		priority_queue<pair<long,int> >P;
		d[_][S[_]]=0;
		w[_][S[_]]=1;
		P.push(make_pair(0,S[_]));
		while(!P.empty())
		{
			long c=-P.top().first;
			int u=P.top().second;
			P.pop();
			if(d[_][u]<c)continue;
			for(pair<int,int>p:G[u])
			{
				int v=p.first;
				long nxt=c+p.second;
				if(d[_][v]>nxt)
				{
					d[_][v]=nxt;
					w[_][v]=w[_][u];
					P.push(make_pair(-d[_][v],v));
				}
				else if(d[_][v]==nxt)(w[_][v]+=w[_][u])%=mod;
			}
		}
	}
	int T=S[1];
	long ans=w[0][T]*w[0][T]%mod;
	for(int i=0;i++<N;)
	{
		if(2*d[0][i]==d[0][T])
		{
			(ans-=w[0][i]*w[0][i]%mod*w[1][i]%mod*w[1][i])%=mod;
		}
	}
	for(int i=0;i<M;i++)
	{
		int u=U[i],v=V[i];
		if(2*d[0][u]<d[0][T]&&2*d[0][v]>d[0][T]&&d[0][u]+D[i]+d[1][v]==d[0][T])
		{
			(ans-=w[0][u]*w[0][u]%mod*w[1][v]%mod*w[1][v])%=mod;
		}
		if(2*d[0][v]<d[0][T]&&2*d[0][u]>d[0][T]&&d[0][v]+D[i]+d[1][u]==d[0][T])
		{
			(ans-=w[0][v]*w[0][v]%mod*w[1][u]%mod*w[1][u])%=mod;
		}
	}
	cout<<(ans+mod)%mod<<endl;
}

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

typedef long long ll;
typedef long double ld;
using namespace std;
//mt19937_64 mrand(chrono::steady_clock::now().time_since_epoch().count());
#define ii for(int i=1;i<=n;++i)
#define ji for(int j=1;j<=n;++j)
#define jj for(int j=1;j<=m;++j)
#define ij for(int i=1;i<=m;++i)
#define sz(x) ((ll)x.size())
#define all(x) x.begin(),x.end()
#define al(x) x+1,x+1+n
#define asd cout<<"ok"<<endl;
#define asdd cout<<"okok"<<endl;
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define pr(v) for(auto i:v) cout<<i<<" ";cout<<endl
#define prt(a, l, r) for(auto i=l;i<=r;++i) cout<<a[i]<<" ";cout<<endl;
#define pc(x) __builtin_popcount(x)
#define pb push_back

const int maxn = 6005;
const int mod = 998244353;
ll dp[maxn][maxn];

ll c2(ll x) {x%=mod;return x*(x-1)/2%mod;}
int main() {
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    dp[a][b]=1;
    for(int i=a;i<=c;++i) {
        for(int j=b;j<=d;++j) {
            if(i==a && j==b) continue;
             dp[i][j] = j*dp[i-1][j]%mod + i*dp[i][j-1]%mod - dp[i-1][j-1]*(i-1)*(j-1)%mod;
             dp[i][j] %= mod;
             if(dp[i][j] < 0) dp[i][j] += mod;
        }
    }
    cout << dp[c][d] << endl;
}

Measured memory_bytes: 85820
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    x = list(map(int, input().split()))
    sum = 0
    for xi in x:
        sum += xi
    ans_1 = sum // n
    ans_2 = sum // n + 1
    score_1 = 0
    score_2 = 0
    for xi in x:
        score_1 += (xi - ans_1) ** 2
        score_2 += (xi - ans_2) ** 2
    print(min(score_1, score_2))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


Measured memory_bytes: 38256
use std::io::{stdin, Read};
use std::str::FromStr;

// https://qiita.com/tubo28/items/e6076e9040da57368845
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[allow(dead_code)]
fn main() {
    let s = read::<String>();
    let k = read::<usize>();
    let n = s.len();
    use std::collections::BinaryHeap;
    let mut b = BinaryHeap::new();
    for w in 0..std::cmp::min(n, k) {
        for i in 0..n - w {
            let item = &s[i..i + w + 1];
            let mut flag = true;

            for &x in b.iter() {
                if x == item {
                    flag = false;
                }
            }
            if flag {
                b.push(item);
                if b.len() > k {
                    b.pop();
                }
            }
        }
    }
    println!("{}", b.pop().unwrap());
}


Measured memory_bytes: 4352
#include<iostream>
#include <set>

using namespace std;

int main() {
    int N; cin >> N;
    
    set<long> s;
    long a;
    for(int i = 0; i < N; i++) {
        cin >> a;
        s.insert(a);
    }

    if (N == s.size()) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}

Measured memory_bytes: 9600
import java.util.Collections;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        Set<Integer> aSet = new HashSet<>();
        for (int i=0;i<k;i++) {
            int d = sc.nextInt();
            for (int j=0;j<d;j++) {
                aSet.add(sc.nextInt());
            }
        }
        int aInt = aSet.size();
        System.out.println(n-aInt);

    }
}


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

int main(){
  int N,ans=1;
  cin >>N;
  vector<int>a(N);
  for(int i=0;i<N;i++)
    cin >> a.at(i);
  sort(a.begin(),a.end());
  reverse(a.begin(),a.end());
  for(int i=1;i<N;i++){
    if(a.at(i)<a.at(i-1))
      ans++;
  }
  cout << ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

template<class T> inline void chmax(T &x, const T &y) {if (x < y) x = y;}

int n;
int happy[100000][3];

int dp[100010][3];

int main()
{
  cin >> n;
  for (int i = 0; i < n; ++i) for (int j = 0; j < 3; ++j) cin >> happy[i][j];
  
  for (int i = 0; i < n; ++i) for (int j = 0; j < 3; ++j) for (int k = 0; k < 3; ++k)
    if (j != k) chmax(dp[i+1][j], dp[i][k] + happy[i][j]);
  
  int ans = 0;
  for (int i = 0; i < 3; ++i) chmax(ans, dp[n][i]);
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 2688
import bisect

N, K = [int(x) for x in input().split()]
V = [int(x) for x in input().split()]
M = min(N, K)

ans = 0
juwel = []
for l in range(M + 1):
    for r in range(M - l + 1):
        juwel = sorted(V[:l] + V[N - r:])
        s = bisect.bisect_left(juwel, 0)
        s = min(s, K - l - r)
        juwel = juwel[s:]
        ans = max(ans, sum(juwel))

print(ans)

Measured memory_bytes: 9184
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
int main(void){
	long long a[100000];
	long long b[100000];
	long long c;
	int n;
	int p;
	int s;
	long long x;
	int y;
	int z;
	c = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		scanf("%lld", &a[i]);
		scanf("%lld", &b[i]);
	}
	for (int i = n-1; i >=0; i--){
		x = (a[i]+c) % b[i];
		if (x != 0)c = c + b[i] - x;
	}
	printf("%lld\n", c);
	return 0;
}

Measured memory_bytes: 1664
n = int(input())
a_list = [int(x) for x in input().split()]
temp_list = [0] * n
temp_list[0] = a_list[0]
for i in range(1, n):
    temp_list[i] = a_list[i] + temp_list[i - 1]
ans = 10 ** 15
for i in range(n - 1):
    temp = abs(temp_list[-1] - (temp_list[i] << 1))
    if temp < ans:
        ans = temp
print(ans)

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

int main() {

  int r, c, i, j;
  int A[101][101] = {};

  cin >> r >> c;

  //??¨???????????¨????¨??????????
  for( i = 0; i < r; i++ ){
    for( j = 0; j < c; j++ ){
      cin >> A[i][j];
      A[i][c] += A[i][j];//??????????¨?
      A[r][j] += A[i][j];//??????????¨?
      A[r][c] += A[i][j];//??¨??????????¨?
    }
  }

  //??°????????¨?????????
  for( i = 0; i <= r; i++ ){
    for( j = 0; j <= c; j++ ){
      cout << A[i][j];
      if( j < c ) cout << " ";
    }
    cout << endl;
  }
  
  return 0;
  
}

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

#define PI 3.14159265359
#define INF 1000000009
#define LINF 1000000000000000009
#define IMOD 1000000007 
#define irep(i,n) for(int i = 0; i < (int)(n); i++)
#define irep2(i,a,n) for(int i = (int)(a); i <= (int)(n); i++)
#define lrep(i,n) for(long long  i = 0; i < (long long)(n); i++)
#define lrep2(i,a,n) for(long long i = (long long)(a); i <= (long long)(n); i++)

#define irrep(i,n) for(int i = (int)(n-1); i > -1; i--)
#define irrep2(i,a,n) for(int i = (int)(n); i >= (int)(a); i--)

typedef long long ll;
typedef std::vector<char> v_char;
typedef std::vector<v_char > v2_char;
typedef std::vector<double> v_double;
typedef std::vector<v_double > v2_double;
typedef std::vector<int> v_int;
typedef std::vector<v_int > v2_int;
typedef std::vector<ll> v_ll;
typedef std::vector<v_ll > v2_ll;
typedef std::vector<std::string> v_string;
typedef std::vector<v_string > v2_string;
typedef std::vector<bool> v_bool;
typedef std::vector<v_bool > v2_bool;
typedef std::pair<ll, ll> pll;
typedef std::pair<int, int> pii;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
using namespace std; 

int main(void)
{
    int R, G, B, N;
    cin >> R >> G >> B >> N;
    
    int ans = 0;
    for(int i = 0; i * R <= N; i++) {
        int r = i * R;
        for(int j = 0; j * G <= N; j++) {
            int g = j * G;
            int b = N - (r+g);
            if(b % B != 0 || b < 0) { continue; }
            if(r+g+b == N) { ans++; }
        }
    }
    cout << ans << endl;
}
/** tcoder **/


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <deque>
#include <queue>
#include <stack>
#include <numeric>
#include <cmath>
#include <map>
#include <set>
#define ull unsigned long long
#define ll long long
using namespace std;



int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,a;
    vector<int> q;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a;
        q.emplace_back(a);
    }
    int ans=0;
    for(int i=0;i<n;i++){
        ans+=q[i]-1;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int read( ){
	int x=0,y=1;char ch=' ';
	for(;(ch!='-' && (ch>'9' || ch<'0'));ch=getchar( ));
	if(ch=='-')y=-1,ch=getchar( );
	for(;ch>='0' && ch<='9';ch=getchar( ))x=x*10+ch-48;
	return x*y;
}
int n;
int main( ){
	int x,y,z,k;
	double ans=0;
	n=read( );
	for(register int i=1;i<=n;++i){
		x=read( );
		ans+=1.0/(double)x;
	}
	printf("%.10lf\n",1.0/ans);
	return 0;
}


Measured memory_bytes: 256
import sys
import numpy as np

stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n, k = nm()
    H = [ni() for _ in range(n)]
    H = np.array(sorted(H))
    dif = H[1:] - H[:-1]
    cum_dif = np.append(0, np.cumsum(dif))
    ans = cum_dif[k - 1:] - cum_dif[:-(k - 1)]
    print(np.min(ans))


if __name__ == '__main__':
    main()


Measured memory_bytes: 32180
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
#define REP(i, a, n) for(int i=a; i<n; i++)
#define F first
#define S second
#define MP(a, b) make_pair(a, b)

int main()
{
	int M, N;
	char field[501][501];
	vector<vector<pair<int, int>>> v(26);
	cin >> M >> N;
	REP(i, 0, M) REP(j, 0, N) {
		cin >> field[i][j];
		if (field[i][j] != '.') {
			v[field[i][j] - 'A'].push_back(MP(i, j));
		}
	}

	int point = 0;
	bool flag = true;
	while (flag) {
		flag = false;
		
		REP(k, 0, 26) {
			if (v[k].size() == 0) continue;
			
			bool del_flag = false;
			int y1 = v[k][0].F, y2 = v[k][1].F;
			int x1 = v[k][0].S, x2 = v[k][1].S;
			int ymin = min(y1, y2), ymax = max(y1, y2);
			int xmin = min(x1, x2), xmax = max(x1, x2);

			if (y1 == y2) {
				REP(l, xmin + 1, xmax) {
					if (field[y1][l] == '.') {
						del_flag = true;
					}
					else {
						del_flag = false;
						break;
					}
				}
			}

			else if (x1 == x2) {
				REP(l, ymin + 1, ymax) {
					if (field[l][x1] == '.') {
						del_flag = true;
					}
					else {
						del_flag = false;
						break;
					}
				}
			}

			else {
				if (field[ymin][xmin] == '.') {
					REP(i, ymin, ymax) {
						if (field[i][xmin] != '.') {
							del_flag = false;
							break;
						}
						else del_flag = true;
					}
					if (del_flag) {
						REP(j, xmin, xmax) {
							if (field[ymin][j] != '.') {
								del_flag = false;
								break;
							}
							else del_flag = true;
						}
					}
				}

				if (!del_flag && field[ymin][xmax] == '.') {
					REP(i, ymin, ymax) {
						if (field[i][xmax] != '.') {
							del_flag = false;
							break;
						}
						else del_flag = true;
					}
					if (del_flag) {
						REP(j, xmin + 1, xmax + 1) {
							if (field[ymin][j] != '.') {
								del_flag = false;
								break;
							}
							else del_flag = true;
						}
					}
				}

				if (!del_flag && field[ymax][xmin] == '.') {
					REP(i, ymin + 1, ymax + 1) {
						if (field[i][xmin] != '.') {
							del_flag = false;
							break;
						}
						else del_flag = true;
					}
					if (del_flag) {
						REP(j, xmin, xmax) {
							if (field[ymax][j] != '.') {
								del_flag = false;
								break;
							}
							else del_flag = true;
						}
					}
				}

				if (!del_flag && field[ymax][xmax] == '.') {
					REP(i, ymin + 1, ymax + 1) {
						if (field[i][xmax] != '.') {
							del_flag = false;
							break;
						}
						else del_flag = true;
					}
					if (del_flag) {
						REP(j, xmin + 1, xmax + 1) {
							if (field[ymax][j] != '.') {
								del_flag = false;
								break;
							}
							else del_flag = true;
						}
					}
				}
			}

			if (del_flag) {
				field[y1][x1] = '.';
				field[y2][x2] = '.';
				v[k].pop_back();
				v[k].pop_back();
				point += 2;
				flag = true;
			}
		}
	}

	cout << point << endl;
	return 0;
}

Measured memory_bytes: 3336
package main

import "fmt"

func main() {
	var n, k int
	fmt.Scan(&n, &k)
	nums := make([]int, n)

	count := 0
	for i, _ := range nums{
		fmt.Scan(&nums[i])
		if nums[i] >= k{
			count++
		}
	}

	fmt.Println(count)
}

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

using ll = long long;
using P = pair<int, int>;

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

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main() {
  char c;
  string s = "";
  for (int i = 0; i < 4; i++) {
    cin >> c;
    s += c;
  }

  cout << ((s.find('1') != string::npos && s.find('9') != string::npos && s.find('7') != string::npos && s.find('4') != string::npos) ? "YES" : "NO") << endl;
  return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;

class Main{
    public static void main(String[] args) throws IOException
    {
        InputStreamReader is = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(is);
        Integer[] data = makeint(br);
        Integer W = data[0], H = data[1], x = data[2], y = data[3], r = data[4];
        if(x >= r && x + r <= W && y >= r && y + r <= H){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
    public static void show(Integer[] a){
        int n = a.length;
        for(int i = 0; i < n - 1; i++){ System.out.print(a[i] + " "); }
        System.out.println(a[n - 1]);
    }
    public static Integer[] makeint(BufferedReader br) throws IOException
    {
        String[] str = br.readLine().split(" ");
        int n = str.length;
        Integer[] a = new Integer[n];
        for(int i = 0; i < n; i++){ a[i] = Integer.parseInt(str[i]); }
        return a;
    }
}


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

using namespace std;

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

    while(d!=0) {
        int n,m;
        vector<int> s;
        int ans=0;

        cin >> n >> m;

        s.push_back(0);

        for(int i=0; i<n-1; ++i) {
            int temp;
            cin >> temp;
            s.push_back(temp);
        }

        s.push_back(d);

        sort(s.begin(),s.end());

        for(int i=0; i<m; ++i) {
            int c,len;
            cin >> c;
            auto itr=upper_bound(s.begin(),s.end(),c);
            len=*itr-c;
            --itr;
            len=min(len,c-*itr);
            ans+=len;
        }

        cout << ans << endl;

        cin >> d;
        s.clear();
    }
    return 0;
}

Measured memory_bytes: 3492
#include <cstdio>

int n,k,a[200010];

int main()
{
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=k+1;i<=n;i++)if(a[i]>a[i-k])printf("Yes\n");
	else printf("No\n");
}

Measured memory_bytes: 2444
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define P pair<long int, long int> 

int main(){
    int n;
    cin >> n;
    long int a[3*n];
    rep(i, 3 * n) cin >> a[i];
    priority_queue<P, vector<P>, greater<P> > q1;
    priority_queue<P> q2;
    priority_queue<P, vector<P>, greater<P> > q3;
    long int c[3*n];
    fill(c, c + 3 * n, 1);
    long int sm1 = 0, sm2 = 0;
    for (int i = 0; i < n; i++){
        q1.push(P(a[i], i));
        sm1 += a[i];
    }
    for (int i = n; i < 3 * n; i++){
        q2.push(P(a[i], i));
        sm2 += a[i];
    }
    for (int i = 0; i < n; i++){
        P p = q2.top();
        q2.pop();
        sm2 -= p.first;
        c[p.second] = 0;
        q3.push(p);
    }
    long int ans = sm1 - sm2;
    for (int i = n; i < 2 * n; i++){

        // rep(i, 3 * n) cout << c[i] << " ";
        // cout << endl;
        // cout << ans << endl;
        if (c[i] == 1){
            sm2 -= a[i];
            P p2 = q3.top();
            q3.pop();
            while(p2.second <= i){
                p2 = q3.top();
                q3.pop();
            }
            sm2 += p2.first;
            c[p2.second] = 1;
        }
        q1.push(P(a[i], i));
        sm1 += a[i];
        c[i] = 1;
        P p1 = q1.top();
        q1.pop();
        sm1 -= p1.first;
        c[p1.second] = 0;
        ans = max(ans, sm1 - sm2);


        
    }

    // rep(i, 3 * n) cout << c[i] << " ";
    // cout << endl;
    cout << ans << endl;


    
    
}

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

int main(){
  int a[3][3]; for(int i=0;i<3;i++) for(int j=0;j<3;j++) cin>>a[i][j];
  int n; cin>>n;
  for(int i=0;i<n;i++) {
    int b; cin>>b;
    for(int i=0;i<3;i++) {
      for(int j=0;j<3;j++) {
        if (a[i][j] == b) a[i][j] = -1;
      }
    }
  }
  bool ok=false;
  if (a[0][0]==-1 && a[1][1]==-1 && a[2][2]==-1) ok=true;
  if (a[2][0]==-1 && a[1][1]==-1 && a[0][2]==-1) ok=true;

  if (a[0][0]==-1 && a[0][1]==-1 && a[0][2]==-1) ok=true;
  if (a[1][0]==-1 && a[1][1]==-1 && a[1][2]==-1) ok=true;
  if (a[2][0]==-1 && a[2][1]==-1 && a[2][2]==-1) ok=true;
  if (a[0][0]==-1 && a[1][0]==-1 && a[2][0]==-1) ok=true;
  if (a[0][1]==-1 && a[1][1]==-1 && a[2][1]==-1) ok=true;
  if (a[0][2]==-1 && a[1][2]==-1 && a[2][2]==-1) ok=true;
  if (ok) cout<<"Yes"<<endl;
  else cout<<"No"<<endl; 
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define LLINF 9223372036854775807
#define MOD ll(1e9+7)

int main(){
    ll n, k;
    cin >> n >> k;

    int max_bit = 31;
    vector<ll> a(n);
    vector<ll> b(n);
    for(int i = 0; i < n; i++){
        cin >> a[i] >> b[i];
    }
    vector<ll> candidates;
    candidates.push_back(k);
    for(int i = 1; i < max_bit; i++){
        if(k&(1<<i)){
            ll tmp = k;
            tmp -= 1<<i;
            tmp |= (1<<i)-1;
            candidates.push_back(tmp);
        }
    }
    ll ans = -1;
    for(int i = 0; i < candidates.size(); i++){
        ll tmpsum = 0;
        for(int j = 0; j < n; j++){
            if((candidates[i]|a[j]) == candidates[i]){
                tmpsum += b[j];
            }
        }
        ans = max(ans,tmpsum);
    }
    cout << ans << endl;

}


Measured memory_bytes: 1792
# coding: utf-8
# Your code here!

s=input()

if(s=='MON'):
    print(6)
elif(s=='TUE'):
    print(5)
elif(s=='WED'):
    print(4)
elif(s=='THU'):
    print(3)
elif(s=='FRI'):
    print(2)
elif(s=='SAT'):
    print(1)
elif(s=='SUN'):
    print(7)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define REP(i,n,N) for(int i=n;i<(int)N;i++)
#define ck(n,a,b) ((a)<=(n)&&(n)<(b))
#define p(s) cout<<(s)<<endl
#define F first
#define S second
typedef long long ll;
using namespace std;

int main() {
	int M, T, P, R;
	while(cin>>M>>T>>P>>R, M||T||P||R){
		int pena[51][11];
		REP(i,0,51) REP(j,0,11) pena[i][j]=0;
//int ok[51][11]={};
//int alltime[51]={};
		pair<int,pair<int,int>> allt[51];
		REP(i,0,51) allt[i]={0,{0,-i-1}};
		//pair<int,int> prob[51];
		//REP(i,0,T) prob[i]={0,-i-1};//p,team
		REP(i, 0, R){
			int m, t, p, j;
			cin>>m>>t>>p>>j;
			t--;
			p--;
			if(j!=0){
				pena[t][p]++;
			}
			else if(j==0){
				allt[t].S.F+=(pena[t][p]*20 + m);
				allt[t].F--;
			}
		}
/*		REP(i, 0, T){
			REP(j, 0, P){
				allt[i].F+=ok[i][j];
			}
		}
*/
		sort(allt, allt+T);
		cout<<-allt[0].S.S;
		REP(i, 1, T){
			if(allt[i-1].F==allt[i].F && allt[i-1].S.F==allt[i].S.F){
				cout<<"="<<-allt[i].S.S;
			}
			else{
				cout<<","<<-allt[i].S.S;
			}
		}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 3068
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb push_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef multiset<ll> S;
typedef priority_queue<ll> PQ;
typedef priority_queue<P,vector<P>,greater<P>> SPQ;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
const ll inf=1001001001001001;
const int INF=1001001001;
const int mod=1000000007;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())outp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size()){rep(j,v[i].size()){if(j)cout<<' ';cout<<v[i][j];}cout<<'\n';}}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){a%=mod;if(b==0)return 1;if(b&1)return a*modpow(a,b-1)%mod;ll k=modpow(a,b/2);return k*k%mod;}
int main(){
    string s;cin>>s;
    ll n=s.size();
    rep(i,n)cout<<'x';
    cout<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int i;
  	vector<int> ar ={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
	cin>>i;
	cout<<ar[i-1]<<endl;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<ll, ll>pll;
const int N = 2e5 + 5;
ll arr[N], ans[N];
vector<int>adj[N];
void dfs(int node, int par, vector<ll>&lis)
{
    bool add = 0;
    ll val = arr[node], idx = -1, old = -1;
    auto it = lower_bound(lis.begin(), lis.end(), val);
    if(it == lis.end())
    {
        add = 1;
        lis.push_back(val);
    }
    else
    {
        old = *it;
        *it = val;
    }
    idx = it - lis.begin();
    ans[node] = (int)lis.size();
    for(auto child : adj[node])
        if(child != par)
            dfs(child, node, lis);
    if(add)
        lis.pop_back();
    else
        lis[idx] = old;
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    for(int i = 1;i <= n;++i)
        cin >> arr[i];
    for(int i = 1;i < n;++i)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<ll>lis;
    dfs(1, 0, lis);
    for(int i = 1;i <= n;++i)
        cout << ans[i] << '\n';
    return 0;
}


Measured memory_bytes: 37860
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
using namespace std;

#define REP(i,n) for(int i=0;(i)<(n);(i)++)
#define ll long long

int main() {
	string S;
	cin >> S;

	int len = S.length();

	int ans = S[0] - 'A';
	if (ans <= 0) ans += 26;
	for(int i=1;i<len;i++) {
		int ad = S[i] - S[i - 1];
		if (ad <= 0) ad += 26;

		//cout << ad << endl;
		ans += ad;
	}

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

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

#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define per(i, a, b) for(int i = (b)-1; i >= (a); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;

const ll mod = 1e9+7;
ll modpow(ll b, ll e) {
  ll ans = 1;
  while (e) {
    if (e&1) ans *= b; ans %= mod;
    b *= b; b %= mod;
    e >>= 1; 
  }
  return ans;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);

  ll n, k;
  cin >> n >> k;
  vector<ll> dp(k+1);

  per(g,1,k+1) {
    ll tot = modpow((k/g), n);
    ll x = 2;

    while (x*g<=k) {
      tot -= dp[x*g];
      tot += mod;
      tot %= mod;
      ++x;
    }

    dp[g] = tot;
  }

  ll ans = 0;
  rep(g,1,k+1)  {
    ans += (g*dp[g])%mod;
    ans %= mod;
  }
  cout << ans << '\n';
}

Measured memory_bytes: 3992
#include <iostream>
#include <string>
#include <algorithm>

int minCount[26];

int main() {
	int n;

	std::cin >> n;

	for (auto&& e : minCount)
		e = 114514;

	for (int i = 0; i < n; ++i) {
		std::string str;
		std::cin >> str;

		std::sort(str.begin(), str.end());

		int seek = 0;
		for (int i = 0; i < 26; ++i) {
			if (seek >= str.size())
				minCount[i] = 0;

			int old = seek;
			while (str[seek] == 'a' + i)
				++seek;

			minCount[i] = std::min(minCount[i], seek - old);
		}
	}

	for (int i = 0; i < 26; ++i)
		for (int j = 0; j < minCount[i] && minCount[i] != 114514; ++j)
			std::cout << static_cast<char>('a' + i);

	std::cout << std::endl;
}

Measured memory_bytes: 256
# N 人
# T秒お湯が出る

N, T = map(int, input().split())

t = list(map(int, input().split()))

start = t[0]
end = t[0] + T
ans = 0
for n in range(0, N):
    # 終わってからボタンを押す
    if end <= t[n]:
        # お湯でた時間を記録
        ans += end - start
        # 初期値をボタンを押したときにする
        start = t[n]
        end = t[n] + T
        
        
    # 最大時間 より先にボタンを押す(追加)
    if end > t[n]:
        end = t[n] + T
    
ans += end - start
print(ans)


Measured memory_bytes: 26708
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int gcd(int* a, int n) {
	int i, g = a[0];
	int calc(int a, int b) {
		return (a % b == 0) ? b : calc(b, a % b);
	}
	for (i = 1; i < n; i++) {
		g = calc(g, a[i]);
	}
	return g;
}

int main() {
	int n, a[100000], i;

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

	printf("%d", gcd(a, n));
}

//redirect
//pipe

Measured memory_bytes: 512
import java.io.PrintWriter;
import java.util.*;

public class Main {

    private static Scanner in = new Scanner(System.in);
    private static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        solve();
        out.flush();
    }

    private static void solve() {
        while(true) {
            int n = in.nextInt();
            int m = in.nextInt();

            if (n == 0 && m == 0)
                break;
            in.nextLine();

            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = in.nextInt();
            }
            Arrays.sort(a);

            int ans = -1;

            for (int i = 0; i < a.length; i++) {
                int item = a[i];
                if (m - item <= 0)
                    break;

                int index = Arrays.binarySearch(a, m - item);
                // out.println("i: " + i + ", index: " + index);
                if (index >= 0 && index != i) {
                    ans = m;
                    break;
                } else {
                    index = ~index - 1;
                    if (index < 0 || index == i)
                        continue;
                    ans = Math.max(ans, item + a[index]);
                }
            }

            out.println(ans == -1 ? "NONE" : ans);
        }
    }

}



Measured memory_bytes: 53272
from sys import stdin


def fetch_one_line():
    return stdin.readline().rstrip()


def fetch_int_input():
    return [int(s) for s in fetch_one_line().split()]


def fetch_inputs(times):
    return [fetch_one_line() for _ in range(times)]


def fetch_int_inputs(times):
    return [[int(s) for s in fetch_one_line()] for _ in range(times)]


def fetch_ints_inputs(times):
    return [fetch_int_input() for _ in range(times)]

N = int(fetch_one_line())
nums = fetch_int_input()

min_num = 999999999999999999
count = 0

for num in nums:
    if min_num >= num:
        count += 1
        min_num = num

print(count)



Measured memory_bytes: 71388
#include<bits/stdc++.h>
using namespace std ;
#define int long long
#define ld long double
#define fast ios_base::sync_with_stdio(false) ;cin.tie(NULL);cout.tie(NULL)
#define F(i,a,b) for(int i= (int)(a); i<(int)(b);i++)
#define FI(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define RF(i,a,b) for(int i = (int)(a); i >= (int)(b); i--)
#define what_is(x) cerr << #x << " is " << x << endl;
#define ms(x,a) memset(x,(int)(a),sizeof(x))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pii pair<int,int>
#define vi vector<int >
#define pb push_back
#define endl '\n'
#define mp make_pair
#define ff first
#define ss second
#define MOD 1000000007
string s ;

int f(int n){
	if(n%4 == 0)
		return n ;
	if(n%4 == 1)
		return 1 ;
	if(n%4 == 2)
		return n+1 ;
	if(n%4 == 3)
		return 0 ;
} 
int32_t main(){fast ;
	int n,m ;
	cin >> n >> m ;
	int res = f(m)^f(n-1) ;
	cout << res << endl ;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<pair<ll, ll>>> vvpll;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

int main() {
    ll n, k;
    cin >> n >> k;

    vl V(n);
    rep(i, n) {
        cin >> V[i]; 
    }

    ll ans = 0;
    exrep(l, 0, min(n, k)) {  // 左からl個取り出す
        exrep(r, 0, min(n, k) - l) {  // 右からr個取り出す
            vl x;  // 手に入れた宝石の価値を入れるvector 
            rep(i, l) {
                x.pb(V[i]);
            }
            for(ll i = n-1; i >= n-r; i--) {
                x.pb(V[i]);
            }
            sort(all(x));
            ll y = k - (l+r);  // 宝石を捨てられる最大回数
            rep(i, min(l+r, y)) {
                if(x[i] < 0) {
                    x[i] = 0;
                }
            }
            ll now = 0;
            rep(i, l+r) {
                now += x[i];
            }
            chmax(ans, now);
        }
    }

    out(ans);
    re0;
}

Measured memory_bytes: 256
(n, m, t) = tuple(map(int, input().split()))
arr = list(map(int, input().split()))
backed = 0
res = 0
for e in arr:
    if e - m > backed:
        res += e - m - backed
    backed = e + m
if arr[-1] + m < t:
    res += t - arr[-1] - m
print(res)



Measured memory_bytes: 5596
//AtCoder-agc003e
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template <typename _Tp> inline _Tp read(_Tp&x){
	char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();
	while(isdigit(c11))x=x*10+c11-'0',c11=getchar();return x;
}

const int N=101000;
ll k[N],a[N],dx[N],n;
int q,top;

int main(){
	read(n),read(q);
	a[top=1]=n;
	for(int i=1;i<=q;++i){
		ll x;read(x);
		while(top&&a[top]>=x)--top;
		a[++top]=x;
	}k[top]=1;
	for(int i=top,id;i;--i){
		ll L=a[i],l;
		while(L>a[1]){
			id=upper_bound(a+1,a+i,L)-a-1;
			l=a[id],k[id]+=k[i]*(L/l),L%=l;
		}dx[L]+=k[i];
	}
	for(int i=n;i;--i)dx[i]+=dx[i+1];
	for(int i=1;i<=n;++i)printf("%lld\n",dx[i]);
	return 0;
}

Measured memory_bytes: 4096
import java.util.Scanner;

// https://atcoder.jp/contests/abc142/tasks/abc142_a
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		sc.close();


		int syo = N/2;

		if(N%2==0) {
			System.out.println((double)syo/N);
		}else {
			System.out.println((double)(syo+1)/N);
		}

	}

}


Measured memory_bytes: 21844
MOD = 10**9 + 7
N = int(input())

ATCG = "ATCG"

memo = {}
def dfs(i, last):
    if i == N:
        return 1
    key = (i, last)
    if key in memo:
        return memo[key]
    p = None
    l2 = last[-2:]
    if l2 == "AC":
        p = "G"
    elif l2 == "AG":
        p = "C"
    elif l2 == "GA":
        p = "C"
    elif last == "AGG" or last == "ATG" or last == "AGT":
        p = "C"
    res = 0
    for c in ATCG:
        if c == p:
            continue
        res += dfs(i+1, last[1:] + c)
    memo[key] = res = res % MOD
    return res
print(dfs(0, "***"))

Measured memory_bytes: 4536
a, b, c, x, y = gets.split.map(&:to_i)
ab = a + b
c2 = c * 2
if ab < c2
  ans = a * x + b * y
else
  m = [x, y].min
  d = (x - y).abs
  ans = c2 * m
  if x == y
  elsif x < y
    m = [c2, b].min
    ans += m * d
  else
    m = [c2, a].min
    ans += m * d
  end
end
puts ans

Measured memory_bytes: 1788
#include<bits/stdc++.h>
const int N=2e5+5;
int n,i,x,y,ans;
char c[N];
int main(){
	scanf("%d%s",&n,c+1);ans=n;
	for(i=1;i<=n;++i)x+=c[i]=='.';
	for(i=0;i<=n;++i)y+=c[i]=='.',ans=std::min(ans,i-y+x-y);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 384