akhauriyash/Code-Regression huggingface dataset:
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aryssoncf
 */

#include <bits/stdc++.h>

using namespace std;

class DWaterBottle {
    const double PI = acos(-1);
    const int ITER = 1'000;

public:
    void solve(std::istream &in, std::ostream &out) {
        int a, b, x;
        in >> a >> b >> x;
        double A = (double) x / a;
        double res = search(0, PI / 2, a, b, A);
        res = f(res);
        out << fixed << setprecision(10) << res << "\n";
    }

    double f(double a) {
        return a / PI * 180;
    }

    double search(double from, double to, double a, double b, double A) {
        for (int i = 0; i < ITER; i++) {
            double ang = (from + to) / 2;
            if (valid(ang, a, b, A)) {
                from = ang;
            } else {
                to = ang;
            }
        }
        return (from + to) / 2;
    }

    bool valid(double alpha, double a, double b, double A) {
        double hleft = a * sinl(alpha), hright = b * cosl(alpha);
        if (hleft >= hright) {
            double h = hright;
            double xright = sqrt(b * b - h * h), xleft = h / tanl(alpha), x = xleft + xright;
            return x * h >= 2 * A;
        }
        double h = hleft;
        double xr = h / tanl(PI / 2 - alpha), xl = sqrt(a * a - h * h), x = xl + xr;
        return x * h / 2 + x * (hright - h) >= A;
    }

    void setup() {}
};


int main() {
    std::ios_base::sync_with_stdio(false);
    DWaterBottle solver;
    solver.setup();
    std::istream &in(std::cin);
    std::ostream &out(std::cout);
    in.tie(nullptr);
    out << std::fixed;
    out.precision(20);
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 512
/*
 
Coded and Decoded by : Yash Kapoor
 
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;

//s.find_by_order(index);
//s.order_of_key(value);
 
#define ll          long long
#define ld          long double
#define pb          push_back
#define pf          push_front
#define mp          make_pair
#define pll         pair<ll,ll>
#define vl          vector<ll>
#define sl          set<ll> 
#define vll         vector<pll>
#define ml          map<ll,ll>
#define mll         map<pll,ll>
#define all(a)      a.begin(),a.end()
#define x           first
#define y           second
#define sz(x)       (ll)x.size()
#define dl          '\n'
#define why         (ll)1000000007
//#define why         (ll)998244353
#define lp(i,a,b)   for(ll i=a;i<b;++i)
#define lpr(i,a,b)  for(ll i=a;i>=b;i--)
#define lpd(i,x)    for(auto i:x)
#define ios         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll inf = 1e18;
ld pi = 3.141592653589;
ll mod = why;
ll fast_power(ll base,ll power,ll mod){
    ll result=1;
    while(power){
        if(power%2)
        result=(result*base)%mod;
        base=(base*base)%mod;
        power/=2;
    }
    return result;
}
 
ll inverse(ll base,ll mod){
    return fast_power(base,mod-2,mod);
}

ll solve(){
    ld a,b,h,m; cin>>a>>b>>h>>m;
    ld mi = h*60 + m;
    ld ha = (0.5)*mi;
    ld ma = (6.0)*mi;
    ld diff = max(ha,ma) - min(ha,ma);
    ld ans = a*a + b*b - 2*a*b*(cos((diff*pi)/180.0));
    cout<<fixed<<setprecision(20)<<sqrt(ans);
    return 0;
}

int main(){
    ios
    ll t=1; 
    //cin>>t;
    while(t--){
        solve();
    }
}  

Measured memory_bytes: 4136
function Main(input) {
	tmp = input.split("\n");
	
	var a = parseInt(tmp[0]);
	var red = 0;
	var blue = 0;
	
	for (var i = 0; i < a; i++){
		if(tmp[1].charAt(i)=="R"){
			red++;
		}
		if(tmp[1].charAt(i)=="B"){
			blue++;
		}
	}
	
	if(red>blue){
		console.log("Yes");
	}else{
		console.log("No");
	}
}

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

Measured memory_bytes: 7372
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(a) (a).begin(),(a).end()
#define overload4(_1, _2, _3, _4, name, ...) name
#define rep1(n) for(ll i = 0;i < (n);i++)
#define rep2(i,n) for(ll i = 0;i < (n);i++)
#define rep3(i,a,b) for(ll i = (a);i < (b);i++)
#define rep4(i,a,b,c) for(ll i = (a);i < (b);i += (c))
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for(ll i = (n)-1;i >= 0;i--)
#define rrep2(i,n) for(ll i = (n)-1;i >= 0;i--)
#define rrep3(i,a,b) for(ll i = (a)-1;i >= (b);i--)
#define rrep4(i,a,b,c) for(ll i = (a)-1;i >= (b);i -= (c))
#define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
const ll INF=1e18,MOD = 1e9+7;
const int iINF = 1e9;

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

    int a;
    cin>>a;
    cout<<a + pow(a,2) + pow(a,3)<<endl;

    return 0;
}


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

int main() {
  int n;
  cin >> n;
  int v[n];
  map<int, int> cnt[2];
  for (int i{}; i < n; ++i) {
    cin >> v[i];
    ++cnt[i % 2][v[i]];
  }

  pair<int, int> maxp[2][2];
  for (int i{}; i < 2; ++i) {
    for (pair<int, int> p : cnt[i]) {
      if (maxp[i][0].second <= p.second) {
        maxp[i][1] = maxp[i][0];
        maxp[i][0] = p;
      } else if (maxp[i][1].second < p.second) {
        maxp[i][1] = p;
      }
    }
  }

  int ansr{};
  if (maxp[0][0].first != maxp[1][0].first) {
    ansr += maxp[0][0].second;
    ansr += maxp[1][0].second;
  } else {
    if (maxp[0][0].second > maxp[1][0].second) {
      ansr += maxp[0][0].second;
      ansr += maxp[1][1].second;
    } else if (maxp[0][0].second < maxp[1][0].second) {
      ansr += maxp[0][1].second;
      ansr += maxp[1][0].second;
    } else {
      if (maxp[0][1].second > maxp[1][1].second) {
        ansr += maxp[0][1].second;
        ansr += maxp[1][0].second;
      } else {
        ansr += maxp[0][0].second;
        ansr += maxp[1][1].second;
      }
    }
  }

  cout << n - ansr << endl;
}


Measured memory_bytes: 5376
# include <bits/stdc++.h>
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define optimize_cin() cin.tie(0); ios::sync_with_stdio(false)
using namespace std;
using lint = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

template<typename Out>
void Split(const std::string &s, char delim, Out result) {
    std::stringstream ss(s);
    std::string item;
    while (std::getline(ss, item, delim)) {
        *(result++) = item;
    }
}

std::vector<std::string> Split(const std::string &s, char delim) {
    std::vector<std::string> elems;
    Split(s, delim, std::back_inserter(elems));
    return elems;
}

int main()
{
    string s1; cin >> s1;
    string s2; cin >> s2;
    string s3; cin >> s3;


    cout << s1[0] << s2[0] << s3[0] << "\n";

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip> // setprecision
#include <cmath>

using namespace std;
typedef long long ll;
const double long PI = acos(-1);

void solve() {
  ll v;
  long double ans;
  cin >> v;
  if (v % 2 == 0)
    ans = 0.5;
  else
    ans = (v / 2 + 1) / (double)v;
  cout << ans << endl;
}

int main(void) {
  cout << fixed << setprecision(10);
  solve();
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
bool vis[100005];
long long dp[100005];
vector<int> v[100005];
long long temp;

void dfs(int dummy){
    vis[dummy] = true;
    for(int i=0; i<v[dummy].size(); i++){
        if(!vis[v[dummy][i]]){
            dfs(v[dummy][i]);
        }
        dp[dummy] = max(dp[dummy], dp[v[dummy][i]] + 1);
    }
}
int main(){
    int N, M, x, y;
    memset(dp, 0, sizeof(dp));
    memset(vis, false, sizeof(vis));
    cin>>N>>M;
    for(int i=0; i<M; i++){
        cin>>x>>y;
        v[x].push_back(y);
    }
    long long temp, ans = 0;
    for(int i=1; i<=N; i++){
        if(!vis[i])
            dfs(i);
    }
    for(int i=0; i<=N; i++)
        ans = max(dp[i], ans);
        
    cout<<ans;
}

Measured memory_bytes: 8576
using System;
using System.Linq;

namespace abc064_a
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
            Console.WriteLine((x[1] * 10 + x[2]) % 4 == 0 ? "YES" : "NO");
        }
    }
}

Measured memory_bytes: 13268
while true do
  n = gets.chomp.to_i
  break if n == 0
  array = []
  n.times do
    ar = gets.chomp.split(" ").map(&:to_i)
    ar << ar[1] * ar[2]
    index = array.index{|arr| arr.first == ar.first}
    if index.nil?
      array << ar
    else
      array[index][1] += ar[1]
      array[index][2] += ar[2]
      array[index][3] += ar[3]
    end
  end
  numbers = array.select{|ar| ar[3] >= 1000000}.map(&:first)
  if numbers.length > 0
    numbers.each do |number|
      puts number.to_s
    end
  else
    puts "NA"
  end
end

Measured memory_bytes: 8872
# -*- coding: utf-8 -*-
import sys
from collections import Counter
# sys.setrecursionlimit(100000)
# input = sys.stdin.buffer.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(S):
    # 2019 = 3 * 673
    L = 2019
    rl = [0] * L
    rl[0] = 1
    ans = 0
    for c in S:
        n = int(c)
        nrl = [0] * L
        nrl[0] = 1
        for r in range(L):
            m = rl[r]
            r = (r * 10 + n) % 2019
            if r == 0:
                ans += m
            nrl[r] += m
        rl = nrl
        # print(rl)

    return ans


def main():
    S = read_str()
    print(slv(S))

    # import random
    # S = ''.join(map(str, random.choices(range(1, 10), k=2*10**5)))
    # print(slv(S))


if __name__ == '__main__':
    main()


Measured memory_bytes: 76892
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int i,n,r=1,a[1000];
int cal(int n)
{
	int i;
	for(i=2;i*i<=n;++i)if(n%i==0)
		for(;n%i==0;n/=i)++a[i];
	if(n>1)++a[n];
}
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;++i)cal(i);
	for(i=2;i<1000;++i)
		r=1ll*r*(a[i]+1)%1000000007;
	printf("%d",r);
}

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

using namespace std;
using ll = long long int;
using lc = complex<double>;

int prs[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};

int main(void) {
    constexpr ll MOD = 1e9 + 7;
    constexpr double PI = acos(-1);
    cout << fixed << setprecision(32);
    cin.tie(0); ios::sync_with_stdio(false);

    ll n;
    cin >> n;
    vector<ll> a(n);
    for(auto &e: a) cin >> e;

    bool pco = true;
    if(pco) {
        set<ll> s;
        for(ll i=0; i<n; i++) {
            ll x = a[i];
            for(ll j=0; j<sizeof(prs)/sizeof(int); j++) {
                if(x == 1) break;
                if(x % prs[j] == 0) {
                    pco &= s.count(prs[j]) == 0;
                    s.insert(prs[j]);
                }
                while(x % prs[j] == 0) x /= prs[j];
            }
            if(x != 1) {
                pco &= s.count(x) == 0;
                s.insert(x);
            }
        }
    }

    if(pco) {
        cout << "pairwise coprime" << endl;
        return 0;
    }

    ll g = 0;
    for(ll i=0; i<n; i++)
        g = __gcd(g, a[i]);
    if(g == 1)
        cout << "setwise coprime" << endl;
    else
        cout << "not coprime" << endl;
}

Measured memory_bytes: 14740
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main() {
    string s; cin>>s;
    int ans=0;
    rep(i,4) ans+=(s[i]=='+' ? 1 : -1);
    cout<<ans<<endl;
}

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

i64 pow(i64 x,int n){
    i64 ans = 1;
    while(n>0){
        if((n&1)==1){
            ans=ans*x%998244353;
        }
        x = x*x%998244353;
        n >>= 1;
    }
    return ans;
}

int main(){
    i64 N,A,B,K;
    cin >> N >> A >> B >> K;
    i64 factorial[N+1],inverse[N+1];
    factorial[0]=1;
    inverse[0]=1;
    repi(i,1,N+1){
        factorial[i]=(factorial[i-1]*i)%998244353;
        inverse[i]=pow(factorial[i],998244353-2)%998244353;
    }
    if(B>A)swap(A,B);
    i64 count = 0;
    for(int i=0;i<=min(K/B,N);i++){
        i64 a = K-B*i;
        if(a%A==0 && a/A<=N){
            count+=(factorial[N]*inverse[i]%998244353*inverse[N-i]%998244353)*(factorial[N]*inverse[a/A]%998244353*inverse[N-a/A]%998244353)%998244353;
        }
    }

    cout << count%998244353 << endl;
    return 0;
}


Measured memory_bytes: 4992
import java.util.*;

class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long x = sc.nextLong();
        long[] values = new long[N+2];

        for (int i = 0; i < N; i++) {
            values[i + 1] = sc.nextLong();
        }

        long ans = 0;
        for (int i = 0; i < N + 1; i++) {
            if (values[i+1] + values[i] > x) {
                long diff = values[i+1] + values[i] - x;
                ans += diff;
                values[i+1] = values[i+1] - diff;
            }
        }
        System.out.println(ans);
    }
}

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


int main(){
        double N,T,A;
        double a[1000];
        double best=100000;
        double sa,best_ad;

        cin>>N;
        cin>>T>>A;
        

        for(int i=0;i<N;i++){
                cin>>a[i];
                a[i]=T-a[i]*0.006;
                if(A>=a[i]){
                        sa=A-a[i];
                }else{
                        sa=a[i]-A;
                }

                if(sa<best){
                        best=sa;
                        best_ad=i+1;
                }
                 //cout<<a[i]<<' '<<sa<<' '<<best<<' '<<best_ad<<endl;
                        }
                        cout<<best_ad<<endl;
        }

Measured memory_bytes: 256
h, w =map(int , input().split()) 
g = [input() for i in range(h)]

if h == 1:
    if w==1:
        if g[0][0]=="#":
            print("#")
        else:
            print("0")
    else:
        wn = ""
        for u in range(w):
            if g[0][u] == ".":
                if u==0:
                    stri = g[0][u+1]
                elif u==w-1:
                    stri = g[0][u-1]
                else:
                    stri = g[0][u-1:u+2]

                wn += str(stri.count("#"))
            else:
                wn += "#"
        print(wn)

elif w == 1:
    for v in range(h):
        wn = ""
        if g[v][0]== ".":
            if v==0:
                stri = g[v+1][0]
            elif v==h-1:
                stri = g[v-1][0]
            else:
                stri = g[v-1][0]+g[v+1][0]
            wn += str(stri.count("#"))
        else:
            wn += "#"
        print(wn)
        
else:
    for s in range(h):
        wn = ""
        for t in range(w):

            if g[s][t] == ".":
                if s==0:
                    if t==0:
                        stri =g[s][t+1]+g[s+1][t:t+2]
                    elif t==w-1:
                        stri = g[s][t-1]+g[s+1][t-1:t+1]
                    else:
                        stri = g[s][t-1:t+2]+g[s+1][t-1:t+2]
                        
                elif s==h-1:
                    if t==0:
                        stri = g[s-1][t:t+2]+g[s][t+1]
                    elif t==w-1:
                        stri = g[s-1][t-1:t+1]+g[s][t-1]
                    else:
                        stri = g[s-1][t-1:t+2]+g[s][t-1:t+2]
                else:
                    if t==0:
                        stri = g[s-1][t:t+2]+g[s][t+1]+g[s+1][t:t+2]
                    elif t==w-1:
                        stri = g[s-1][t-1:t+1]+g[s][t-1]+g[s+1][t-1:t+1]
                    else:
                        stri = g[s-1][t-1:t+2]+g[s][t-1]+g[s][t+1]+g[s+1][t-1:t+2]

                wn += str(stri.count("#"))
            else:
                wn += "#"

        print(wn)

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

int main()
{
    std::string a, b;
    std::cin >> a >> b;
    long long num;
    num = std::stoi(a + b);
    for (int i = 1; i < 400; ++i)
    {
        if (num == std::pow(i, 2))
        {
            std::cout << "Yes" << std::endl;
            return 0;
        }
    }
    std::cout << "No" << std::endl;
    return 0;
}


Measured memory_bytes: 256
import math
import fractions
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

#最小公倍数
def union_lcm(lists):
    if len(lists)==1:
        return lists[0]
    elif len(lists)>1:
        num=lists[0]
        for i in range(1,len(lists)):
            num=num*lists[i]//fractions.gcd(num,lists[i])
        return num


#最大公約数
def union_gcd(lists):
    if len(lists)==1:
        return lists[0]
    elif len(lists)>1:
        num=lists[0]
        for i in range(1,len(lists)):
            num=fractions.gcd(num,lists[i])
        return num
mod=10**9+7   
n=int(input())
lists=list(map(int,input().split()))
a=union_lcm(lists)
c=0
a=a%mod
for i in range(n):
    c+=a*modinv(lists[i],mod)
    c=c%mod
print(c)


Measured memory_bytes: 6136
#include <iostream>
#include <cstdlib>
#include <algorithm>

using namespace std;

// change minimumのこと
// a>bならばaにbを代入し、trueを返す
// 他の場合はfalseを返す
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;
}

const long long INF = 1LL << 60;
const long long P = 1000000007;

int main() {
  int n,m;
  cin >> n >> m;
  int a[n];
  long long dp[n+1];
  bool floor[n+1];
  for(int i = 0; i <= n; i++) {
    dp[i] = 0;
    floor[i] = true;
  }
  for(int i = 0; i < m; i++) {
    cin >> a[i];
    floor[a[i]] = false;
  }
  dp[0] = 1;
  // dp[i]を確定させ、dp[空いた階段]は0のままにする
  for(int i = 0; i < n; i++) {
    for(int j = i+1; j <= min(n,i+2); j++) {
      if(floor[j]) {
        dp[j] += dp[i];
        dp[j] %= P;
      }
    }
  }
  cout << dp[n] << endl;
  return 0;
}

Measured memory_bytes: 1536
import Control.Arrow
import Data.Bits
import Data.Char
import Data.List

main :: IO ()
main = do
  xs <- getInts
  k <- getInt
  let m = maximum xs
  print $ sum xs + m * (2 ^ k - 1)

getInt :: IO Int
getInt = readLn

getInts :: IO [Int]
getInts = map read . words <$> getLine


Measured memory_bytes: 508
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime> 
#include <memory.h>
#include <assert.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9 + 1;
const ll LLINF = 1e18 + 1;

int main() {
    int N;
    cin >> N;
    int ma = -1;
    int ans = 0;
    for(int i = 0; i < N; i++) {
        int H;
        cin >> H;
        if (H >= ma) {
            ma = H;
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}

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


int main(){
    int n,k;
    cin>>n>>k;
    vector<int>v(n),dp(n,INT_MAX);
    for(int i = 0 ; i < n ; i++){
        cin>>v[i];
    }
    dp[0]=0;
    for(int i = 1 ; i < n ; i++ ){
        for(int j= i-1 ; j >= max(0,i-k) ; j--)
        dp[i]=min(dp[i],dp[j]+abs(v[i]-v[j]));
    }
    cout<<dp[n-1];
    
}


Measured memory_bytes: 4028
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;

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

        static void Method(string[] args)
        {
            long[] ab = ReadLongs();
            long a = ab[0];
            long b = ab[1];
            long div = 2;
            long val = 0;
            for(int i = 0; i < 50; i++)
            {
                long cnt = (b / div) * (div / 2);
                if (b % div > div / 2 - 1)
                {
                    cnt += b % div - (div / 2 - 1);
                }
                if (a > 0)
                {
                    cnt -= ((a - 1) / div) * (div / 2);
                    if ((a - 1) % div > div / 2 - 1)
                    {
                        cnt -= (a - 1) % div - (div / 2 - 1);
                    }
                }
                if (cnt % 2 == 1)
                {
                    //WriteLine(div / 2);
                    val += div / 2;
                }
                div *= 2;
            }
            WriteLine(val);
        }

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


Measured memory_bytes: 13268
import sys
n,k=map(int,input().split())
m1=list(map(int,input().split()))
m2=[]
imos=[0]*(n+1)
counter=0
while counter<=k:
  counter+=1
  if counter%2==1:
    m2=[]
    imos=[0]*(n+1)
    for i in range(n):
      imos[max(0,i-m1[i])]+=1
      imos[min(n,i+m1[i]+1)]-=1
    current=0
    for i in range(n):
      current+=imos[i]
      m2.append(current)
    sameflag=1
    for i in range(n):
      if m1[i]!=m2[i]:
        sameflag=0
        break
    if sameflag==1:
      for i in range(n):
        m2[i]=str(m1[i])
      print(' '.join(m2))
      sys.exit()
  else:
    m1=[]
    imos=[0]*(n+1)
    for i in range(n):
      imos[max(0,i-m2[i])]+=1
      imos[min(n,i+m2[i]+1)]-=1
    current=0
    for i in range(n):
      current+=imos[i]
      m1.append(current)
    for i in range(n):
      if m1[i]!=m2[i]:
        sameflag=0
        break
    if sameflag==1:
      for i in range(n):
        m2[i]=str(m1[i])
      print(' '.join(m2))
      sys.exit()
if k%2==0:
  for i in range(n):
    m2[i]=str(m1[i])
  print(' '.join(m2))
else:
  for i in range(n):
    m1[i]=str(m2[i])
  print(' '.join(m1))

Measured memory_bytes: 184912
#include <iostream>
#include <iomanip>
#include<math.h>
#include<list>
#include <algorithm>
#include<set>
#include<vector>
#include<math.h>
#include<map>
#include<string>
#include <numeric>
#include <queue>
#include <sstream>

using namespace std;
using ll = long long;
using vll = vector<long long>;
using sll = set<long long>;

template<typename T>
T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }

template<typename T>
map<T, T> primeFactor(T n) {
	map<T, T> res;
	for (T i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			res[i] ++;
			n /= i;
		}
	}
	if (n != 1) res[n] = 1;
	return res;
}

template<typename T>
bool IsPrimeNumber(T num)
{
	if (num <= 2) return true;
	else if (num % 2 == 0) return false;

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			return false;
		}
	}

	return true;
}


#define in(x) cin >> x
#define out(x) cout << x
#define outn(x) cout << x << '\n'
#define outs(x) cout << x << ' '
#define rep(i,s,e) for(long i=s;i<e;i++)
#define repeq(i,s,e) for(long i=s;i<=e;i++)



int main() {

	ll n, h,tmp,d=0,ans=0,cnt=0;
	in(n);
	in(h);

	vector<pair<ll,ll>> a(2*n);
	rep(i, 0, n) {
		in(tmp);
		a[i] = make_pair(tmp, i);
		in(tmp);
		a[i+n] = make_pair(tmp, n+i);
	}
	sort(a.begin(), a.end(), greater<pair<ll, ll>>());

	while (0 < h) {

		if (a[cnt].second < n) {
			ans += h / a[cnt].first;
			if (h % a[cnt].first != 0) {
				ans++;
			}
			break;
		}

		ans++;
		h -= a[cnt].first;

		cnt++;
	}

	outn(ans);

	return 0;

}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
#include<vector>
#include<string>
#include<stack>
#include<iostream>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define vec(a) vector<int>a
using namespace std;
//fibonacci
int binet(int n)
{
	return (pow((1+sqrt(5)),n-1)-pow((1-sqrt(5)),n-1))/(pow(2,n-1)*sqrt(5));
}


int main()
{
#ifndef ONLINE_JUDGE
	freopen("output.txt", "w", stdout);
	freopen("input.txt", "r", stdin);
#endif
	fastio
	char ch;
  	cin>>ch;
  	cout<<char(int(ch)+1)<<"\n";
	return 0;
}
	

Measured memory_bytes: 3508
#include <iostream>
#include <stdio.h>

#include <vector>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;


int main()
{
    int n, m;
    long long k;

    cin >> n >> m >> k;

    vector<long long> a(n);

    vector<long long> b(m);

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

    for (int i = 0; i < m; i++)   cin >> b[i];
    

    //aとbの先頭を比較して、小さいほうを引いていく。
    //Kから引いて行って、残っている最小よりもKが小さくなったらカウント終了
    //上の考え方はよくなかった
    //abの組み合わせを求める問題と読み換えるのが正解
    
    int count = 0;
   
    vector<long long> suma(n + 1);
    vector<long long> sumb(m + 1);
    
    suma[0] = 0;
    sumb[0] = 0;

    for (int i = 1; i <= n; i++) suma[i] = a[i-1]+suma[i - 1];
    for (int i = 1; i <= m; i++) sumb[i] = b[i-1]+sumb[i - 1];
    /*
    int i = 0;
    int begin = m;
    int count1 = 0;
    while (i <= n) {
        
        for (int j = begin; j >= 0; j--) {
            if (k >= suma[i] + sumb[j]) {
                count1 = i + j;
                begin = j;
                break;
            }
        }

        if (count < count1) count = count1;
        i++;
    }
    */
    
    int begin = m;
    for (int i = 0; i < n + 1; i++) {

        if (suma[i] > k) {
            break;
        }

        int count1 = 0;

        for (int j = begin; j >= 0;j--) {
            if (k>=suma[i]+sumb[j]) {
                count1 = i + j;
                begin = j;
                break;
            }
        }
        if (count<count1) count = count1;

    }

    std::cout << count << endl;   

    return 0;
}


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

int main(){
  int w;
  string s;
  cin >> s>>w;
  r(i,s.length()){
    cout <<s.at(i);
    i+=w-1;
  }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<string>
using namespace std;
#define MAXN 100110
typedef long long ll;

ll a[MAXN];
ll b[MAXN];
ll c[MAXN];
ll ba[MAXN];
ll bb[MAXN];

int main()
{
	ll i,j,k;
	ll n;
 	scanf("%lld",&n);
 	for(i=0;i<n;i++)scanf("%lld",&a[i]);
 	for(i=0;i<n;i++)scanf("%lld",&b[i]);
 	for(i=0;i<n;i++)scanf("%lld",&c[i]);
 	
 	sort(a,a+n);
 	sort(b,b+n);
 	sort(c,c+n);
 	
 	
 	j=0;
 	ll cnt=0;
 	for(i=0;i<n;i++)
 	{
	 	while(b[i]>a[j]&&j<n)
	 	{
	 		cnt++;
	 		j++;
	 	}
	 	ba[i]=cnt;
	 }
	 
	 j=n-1;
 	cnt=0;
 	for(i=n-1;i>=0;i--)
 	{
	 	while(b[i]<c[j]&&j>=0)
	 	{
	 		cnt++;
	 		j--;
	 	}
	 	bb[i]=cnt;
	 }
	 
 	
 	long long sum=0;
 	
	 for(i=n-1;i>=0;i--)
	 {
 		sum+=ba[i]*bb[i];
 	}
	 
	 printf("%lld\n",sum);
	 
} 

Measured memory_bytes: 4224
#include <bits/stdc++.h>
using namespace std;
#define rep0(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
using ll = long long;

int main(){
    string s;cin>>s;
    int a=0,b=0;
    int l=s.size();
    if(l%2==0){
        rep0(i,l/2){
            if(s[2*i]=='0'){
                a++;
            }
            else{
                b++;
            }
          
        }
        rep0(i,l/2){
            if(s[2*i+1]=='1'){
                a++;
            }
            else{
                b++;
            }
        }
        }
        else{
            rep0(i,l/2){
            if(s[2*i]=='0'){
                a++;
            }
            else{
                b++;
            }
         
        }
        rep0(i,l/2){
            if(s[2*i+1]=='1'){
                a++;
            }
            else{
                b++;
            }
        }
        if(s[l-1]=='0'){
            a++;
        }
        else{
            b++;
        }
        }
    cout<<min(a,b)<<endl;
}

Measured memory_bytes: 512
n, k = map(int, input().split())
s = list(input())

if s[k-1] == "A":
  s[k-1] = "a"
elif s[k-1] == "B":
  s[k-1] = "b"
else:
  s[k-1] = "c"

for i in range(n):
  print(s[i], end="")

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <regex>

#define FOR(i, f, n) for(int (i) = (f); (i) < (n); (i)++)
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (n); (i)--)
#define REP(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define RREP(i, n) for(int (i) = (n); (i) >= 0; (i)--)
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define rrep(i, n) for(int (i) = (n); (i) >= 0; (i)++)
#define p(...) printf(__VA_ARGS__); cout << endl;
#define in(...) __VA_ARGS__; input__(__VA_ARGS__);
#define input(...) in(__VA_ARGS__)
#define out(...) output__(__VA_ARGS__);
#define output(...) out(__VA_ARGS__)
#define list_input(x, n) x[(n)]; for(int (i) = 0; (i) < (n); (i)++) cin >> x[i];
#define lambda(a, b, c) [](const a, const b){ return c ;}
#define key(t, x, compare) [](const t& a, const t& b){ return a x compare b x ;}

using namespace std;

using pii = pair<int, int>;

template <class... T>
void input__(T &...a) {
  for(auto v: {&a...}) {
    cin >> *v;
  }
}

void output__(){
  cout << endl;
}

template <class Head, class... T>
void output__(Head const &v, T const &...a) {
  if(sizeof...(a) == 0) {
    cout << v;
  } else {
    cout << v << " ";
  }
  output__(a...);
}

int main(){
  int in(n);
  long long nowx = 0, nowy = 0, nowt = 0;
  rep(i, n) {
    int in(t, x, y);
    int diff = t - nowt,
        dx = abs(nowx - x),
        dy = abs(nowy - y),
        d = dx + dy,
        result = diff - d;
    if(not (result >= 0 and not (result & 1))) {
      out("No") return 0;
    }
  }

  out("Yes");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,N) for(int i=0;i<N;i++)
#define rep2(i,N) for(int i=1;i<=N;i++)
using namespace std;
long long  INF=1000000000000000000;
long long mod=1000000007;
using namespace std;


int main(){

long long  N,A,B;
cin>>N>>A>>B;
long long ans=1e18;
if((B-A)%2==0){
    ans=(B-A)/2;
}
else if (N-B<A-1){
    ans=N-B;
    ans+=(B-A+1)/2;
}
else{
    ans=A-1;
    ans+=(B-A+1)/2;
}
cout<<ans<<endl;



return 0;

}
/*
5 2 4

1


5 2 3

2

*/


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <string>

using namespace std;

typedef long long LL;
typedef unsigned int UI;

#define rSort(a) 		sort(a.rbegin(),a.rend())
#define Sort(a) 		sort(a.begin(),a.end())
#define Reverse(a) 		reverse(a.begin(),a.end())
#define Sum(a)  		accumulate(a.begin(), a.end(), 0)
#define REP(i, n) 		for(UI i = 0;i < n;i++)
#define REPR(i, n) 		for(UI i = n;i >= 0;i--)
#define FOR(i, m, n) 	for(UI i = m;i < n;i++)
#define pb(i) 			push_back(i)

#define MOD  			(LL)1e9 + 7;
#define INF  			(LL)1 << 62;

int main(int argc, const char * argv[]) {

	cin.tie(0);
	ios::sync_with_stdio(false);

	string S;
	int cnt = 0;

	cin >> S;

	for(int i=0;i<S.length();i++){
		if(S[i]=='x'){
			cnt++;
		}
	}

	if (cnt > 7) {
		cout << "NO" << endl;
	}else{
		cout << "YES" << endl;
	}

	return 0;

}

Measured memory_bytes: 256
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <iostream>
#include <fstream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <set>
#include <map>
#include <functional>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
using namespace std;
#define ll           long long
#define all(v)       (v).begin() , (v).end()
#define vi           vector <ll>
#define vii          vector <pair<ll,ll>>
#define ii           pair<ll,ll>
#define sz(v)	     ((int)((v).size()))
#define lp(i,a,b)    for(int i=a;i<b;i++)
#define pb           push_back
#define pf           push_front
#define F            first
#define S            second
#define endl         "\n"
#define IOS          ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const double PI = 3.14159265358979323846;
const ll inf=2e9,MOD=998244353,MAX=1e7+2;

vector<int>cnt(MAX,1);

void seive(){
    lp(i,2,MAX){
        for(int j=i;j<MAX;j+=i)
            cnt[j]++;
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    IOS;
    seive();
    int n;
    cin>>n;
    ll res=0;
    for(ll i=1;i<=n;i++)
        res+=i*cnt[i];
    cout<<res;
}

Measured memory_bytes: 42192
url = "https://atcoder.jp//contests/abc094/tasks/abc094_a"

def main():
    t = list(map(int, input().split()))
    for i in range(t[1]):
        tmp = i + t[0]
        if tmp == t[2]:
            print('YES')
            exit()
    print('NO')

if __name__ == '__main__':
    main()


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

using namespace std;

int main(){
	string a;
	string b;
	cin >> a >> b;
	auto contain = [&](string need){
		if(need.empty())return true;
		int itr = 0;
		for(char i:b){
			if(need[itr]==i){
				++itr;
				if(itr==need.size()){
					return true;
				}
			}
		}
		return false;
	};
	string need1 = "";
	string need2 = "";
	for(int i=0;i<a.size();++i){
		if(i&1){
			need1 += a[i];
		}else{
			need2 += a[i];
		}
	}
	cout << ((contain(need1) or contain(need2)) ? "Yes" : "No") << endl;
	return 0;
}



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

int main() {
  int n,m,x,y;
  cin>>n>>m>>x>>y;
  int left=-100;
  int right=100;
  for(int i=0;i<n;i++){
    int a;
    cin>>a;
    left=max(a,left);
  }
  for(int i=0;i<m;i++){
    int b;
    cin>>b;
    right=min(b,right);
  }
  string ans="War";
  for(int i=x+1;i<=y;i++){
    if(left<i && i<=right) ans="No War";
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
        int n,sf,ss=0;
        scanf("%d",&n);
        int a[n];
        sf=0;
        for(int i=0;i<n;i++){
                scanf("%d",&a[i]);
                if(a[i]>sf){
                        sf=a[i];
                        //printf("SF=%d\n",sf);
                }else if(a[i]>ss){
                        ss=a[i];
                        //printf("SS=%d\n",ss);
                }
        }
        //printf("SF=%d SS=%d\n",sf,ss);
        for(int i=0;i<n;i++){
                if(sf==a[i]){
                        printf("%d\n",ss);
                }else{
                        printf("%d\n",sf);
                }
        }
        return 0;
}

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

#define rep(i, n) for (int i=0; i<n; ++i)

int main(void){
  int x, a;
  cin >> x >> a;
  
  if (x < a) {
    cout << 0 << endl;
  } else {
    cout << 10 << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long
#define ll long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define lb lower_bound
#define IOS cin.tie(0); ios::sync_with_stdio(false)
using namespace std;
int gcd(int a,int b){return b ? gcd(b,a%b) : a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}

main() {
    int A,B; cin >> A >> B;
    int Q; cin >> Q;
    vector<ll> s,t;
    rep(i,2) s.push_back(-99999999999);
    rep(i,2) t.push_back(-99999999999);
    rep(i,A) {int a; cin >> a; s.push_back(a);}
    rep(i,B) {int b; cin >> b; t.push_back(b);}
    rep(i,2) s.push_back(99999999999);
    rep(i,2) t.push_back(99999999999);
    sort(s.begin(),s.end()); sort(t.begin(),t.end());
    rep(i,Q){
        ll x; cin >> x;
        ll a=(ll)(*lb(s.begin(),s.end(),x));
        ll b=(ll)(*(lb(s.begin(),s.end(),x)-1));
        ll c=(ll)(*lb(t.begin(),t.end(),x));
        ll d=(ll)(*(lb(t.begin(),t.end(),x)-1));
        cout << min({max(a,c)-x,x-min(b,d),
        min(a-x,x-d)*2+max(a-x,x-d),
        min(x-b,c-x)*2+max(x-b,c-x)});
        cout << endl;
    }
}

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

using namespace std;

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

	long long n;
	cin >> n;
	long long cur;
	for (cur = 1; cur * cur < n; cur++);
	long long oth = n;
	for (; cur > 0; cur--) {
		if (n % cur == 0) {
			oth = n / cur;
			break;
		}
	}
	int res = 0;
	while (oth) {
		oth /= 10;
		res++;
	}
	cout << res << '\n';

	return 0;
}



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

using namespace std;
typedef long long ll;
typedef pair<int,int>pa;
map<pa,int>mp;
const int N=2e5+100;

int fa1[N],fa2[N];
int _find1(int x)
{
    if(fa1[x]==x)
        return fa1[x];
    return fa1[x]=_find1(fa1[x]);
}
int _find2(int x)
{
    if(fa2[x]==x){
        return  fa2[x];
    }
    else {
        return fa2[x]=_find2(fa2[x]);
    }
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n,k,l;
    cin>>n>>k>>l;
    for(int i=1;i<=n;i++)
    {
        fa1[i]=i;
        fa2[i]=i;
    }
    for(int i=1;i<=k;i++){
        int a,b;
        cin>>a>>b;
        int aa=_find1(a);
        int bb=_find1(b);
        if(aa!=bb) fa1[aa]=bb;
    }
    for(int i=1;i<=l;i++){
        int a,b;
        cin>>a>>b;
        a=_find2(a);
        b=_find2(b);
        if(a!=b) fa2[a]=b;
    }
    for(int i=1;i<=n;i++){
        _find1(i);
        _find2(i);
    }
    for(int i=1;i<=n;i++){
        mp[make_pair(fa1[i],fa2[i])]++;
    }
    for(int i=1;i<=n;i++){
        cout<<mp[make_pair(fa1[i],fa2[i])]<<" ";
    }
    return 0;
}


Measured memory_bytes: 16504
/*BISMILLAH
THE WHITE WOLF
NO DREAM IS TOO BIG AND NO DREAMER IS TOO SMALL*/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<long long> vll;
typedef vector<int> vi;

#define io ios_base::sync_with_stdio(false)
#define pb push_back
#define eb emplace_back
#define mod   998244353
#define PI 2*acos(0.0)
int dirx[] = {1, -1,0, 0}, diry[] = {0, 0, 1, -1};
//======================================ASIFAZAD==========================================//

const int N = 200010;
int fac[N];

ll bigmod(ll x, ll p)
{
    ll res = 1;
    while(p)
    {
        if(p&1)
            res = (res*x)%mod;
        x = (x*x)%mod;
        p >>= 1;
    }
    return res;
}

ll ncr(int n, int r)
{
    return (fac[n] * (bigmod(1LL*fac[r]*fac[n-r]%mod, mod-2))%mod)%mod;
}

int32_t main()
{
    io;
    fac[0] = 1;
    for(int i = 1; i <N; i++)
        fac[i] = (1LL*fac[i-1]*i)%mod;
    int n, m, k;
    cin>>n>>m>>k;
    ll ans = 0;
    for(int i = 0; i<= k; i++)
    {
        (ans += ncr(n-1, i)*bigmod(m-1, n-1-i)%mod*m) %= mod;
    }
    cout<<ans%mod;
    return 0;
}

Measured memory_bytes: 4336
#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cctype>
#include<map>
#include<cstring>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,b) for (int (i)=a;(i)<(b);(i)++)
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long int;

const int inf = 1001001000;
const long long int Inf = 1001001001001001000;



void print(vector<vector<int>> a){
	for (int i = 0; i < a.size(); i++)
	{
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<vector<long long int>> a){
	for (int i=0;i<a.size();i++){
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(vector<long long int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(set<int> a){
	for (auto x:a)
		cout << x << " ";
	cout << endl;
}

//mod計算用のクラス
class ModInt{
public:
    long long int x;
    long long int mod;
	ModInt(){}
    ModInt(long long int _x, long long int _mod = 1000000007){
        this->x = _x % _mod;
        this->mod = _mod;
    }
	ModInt operator+(ModInt other){
		return ModInt(this->x + (other.x % this->mod),this->mod);
	}
	ModInt operator-(ModInt other){
		long long int res = this->x - (other.x % this->mod);
		if (res < 0) return ModInt(res + this->mod, this->mod);
		return ModInt(res);
	}
	ModInt operator*(ModInt other){
		return ModInt(this->x * (other.x % this->mod),this->mod);
	}
	ModInt operator/(ModInt other){
		return ModInt(*this * other.inv());
	}
	ModInt pow(long long int n){
		ModInt res(1, this->mod), a(this->x, this->mod);
		while (n){
			if (n & 1){
				res = res * a;
			}
			n >>= 1;
			a = a * a;
		}
		return res;
	}
	ModInt inv(){
		return ModInt(this->pow(this->mod - 2));
	}
	void disp(){
		cout << this->x << endl;
	}
};
ostream& operator<<(ostream& stream, const ModInt m){
	stream << to_string(m.x);
	return stream;
}

int main()
{
	int n, k;
	cin >> n >> k;
	vector<ModInt> d(k+1);
	rep(i,k){
		d[i + 1] = ModInt(k / (i + 1)).pow(n);
	}
	for (int i = k; i > 0; i--)
	{
		for (int j = 2 * i; j < k + 1; j += i)
		{
			d[i] = d[i] - d[j];
		}
	}
	ModInt ans(0);
	rep(i,k){
		ans = ans + (d[i + 1] * ModInt(i + 1));
	}
	cout << ans << endl;

	return 0;
}

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

using namespace std;

int main() {
    
    set<int> s;
    int x,n;
    cin >> x >> n;

    for (int i = -200; i <= 200; ++i)
        s.insert(i);

    for (int i = 0; i < n; ++i) {
        int z;
        cin >> z;
        s.erase(z);
    }

    auto p = s.lower_bound(x);

    auto p2 = p;
    if(s.begin() != p2) p2--;

    if(abs(*p - x) < abs(*p2 - x)) cout << *p << "\n";
    else cout << *p2 << "\n";
    return 0;
}


Measured memory_bytes: 3620
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <tr1/unordered_set>
using namespace std;
using namespace tr1;

#define REP(i,a,n) for(i=a; i<n; i++)
#define rep(i,n) REP(i,0,n)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define foreach(it,x) for(typeof(x.begin()) it=x.begin(); it!=x.end(); it++)

typedef long long ll;

const int dx[] = {0,1,0,-1};
const int dy[] = {-1,0,1,0};
int w,h, tatu_x[20], tatu_y[20], kazu_x[20], kazu_y[20];
int field[12][12], cx[36], cy[36], csize;
map<pair<int,int>, int> idx;
unordered_set<ll> visited[20][4][2];


bool inside(int x, int y){
    return !(x < 0 || x >= w || y >= h || y < 0 );
}

bool backtrack(int cnt, ll kS, int init_dir, int f){
    int i,j,k;

    if( visited[cnt][init_dir][f].count(kS) ) return false;
    if( csize/2 == cnt ) return true;

    rep(i,cnt){ // ツ達ツ姪ァツづ個チツδコツつゥツづァツ新ツつオツつ「ツ偲シツ陛督づ個チツδコツづーツ選ツ妥ー
        rep(k,4){
            int tx = tatu_x[i] + dx[k];
            int ty = tatu_y[i] + dy[k];
            if( !inside(tx,ty) || field[ty][tx] == 0 ) continue;

            // ツ妥篠可楪つキツづゥツ和ツ姪ァツづ個チツδコ
            int ttx = kazu_x[i] + dx[(k + init_dir + (f?2:0)) % 4];
            int tty = kazu_y[i] + dy[(k + init_dir) % 4];
            if( (tx == ttx && ty == tty) || !inside(ttx,tty) || field[tty][ttx] == 0 ) continue;

            field[ty][tx] = 0;
            tatu_x[cnt] = tx, tatu_y[cnt] = ty;

            field[tty][ttx] = 0;
            kazu_x[cnt] = ttx, kazu_y[cnt] = tty;

            if( backtrack(cnt+1, kS|(1LL<<idx[make_pair(ttx,tty)]), init_dir, f) ) return true;
            field[tty][ttx] = 1;
            field[ty][tx] = 1;
        }
    }
    visited[cnt][init_dir][f].insert(kS);
    return false;
}

bool solve(){
    int i,j,k;

    if( csize % 2 ) return false;

    // ツ達ツ姪ァ
    tatu_x[0] = cx[0], tatu_y[0] = cy[0];
    field[cy[0]][cx[0]] = 0;

    REP(j,1,csize){ // ツ和ツ姪ァ
        kazu_x[0] = cx[j], kazu_y[0] = cy[j];
        field[cy[j]][cx[j]] = 0;

        rep(k,4){
            if( backtrack(1, 1LL<<j, k, 0) ) return true;
            if( backtrack(1, 1LL<<j, k, 1) ) return true;
        }
        field[cy[j]][cx[j]] = 1;
    }
    field[cy[0]][cx[0]] = 1;

    return false;
}

int main(){
    int i,j,k,u;

    while( cin >> w >> h, w|h ){
        // init
        idx.clear();
        rep(i,20) rep(j,4) rep(k,2) visited[i][j][k].clear();
        csize = 0;

        // input
        rep(i,h) rep(j,w){
            cin >> field[i][j];
            if( field[i][j] == 1 ){
                cx[csize] = j, cy[csize] = i;
                idx[make_pair(j,i)] = csize;
                csize++;
            }
        }
        puts( solve() ? "YES" : "NO" );
    }

    return 0;
}

Measured memory_bytes: 0
import sys
input = sys.stdin.readline
def gcd(a, b):
    while b: a, b = b, a % b
    return a

N = int(input())
S = 0
Y = []
for i in range(N):
    a, b = map(int, input().split())
    if b > a:
        S += b-a
        Y.append((b, b))
    else:
        Y.append((a, b))

Y = sorted(Y)
YY = [0] * (N+1)
for i in range(N):
    YY[i+1] = YY[i] + Y[i][0]

# i番目を除いてn個選ぶときの余裕度
def f(i, n):
    return S - Y[i][0] + Y[i][1] - (YY[n] if n <= i else YY[n+1] - Y[i][0])

ma1, ma2 = 0, 1
for i in range(N):
    l = 0
    r = N
    while r - l > 1:
        m = (l+r) // 2
        if f(i, m) >= 0:
            l = m
        else:
            r = m

    a = l * Y[i][1] + min(f(i, l), Y[i][1])
    b = N * Y[i][1]
    if a * ma2 > b * ma1:
        ma1, ma2 = a, b

g = gcd(ma1, ma2)
print(ma1//g, ma2//g)

Measured memory_bytes: 21604