akhauriyash/Code-Regression huggingface dataset:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

uf = UnionFind(N)
AB = [list(mapint()) for _ in range(M)][::-1]
ans = [0]*M
ans[0] = N*(N-1)//2
groups = N*(N-1)//2
for i in range(M-1):
    a, b = AB[i]
    if not uf.same(a-1, b-1):
        a_size = uf.size(a-1)
        b_size = uf.size(b-1)
        uf.union(a-1, b-1)
        groups -= a_size*b_size
    ans[i+1] = groups
for a in ans[::-1]:
    print(a)

Measured memory_bytes: 97400
#pragma GCC optimize("O2")

#include <bits/stdc++.h>
#ifdef DEBUG
    #include "debug.hpp"
#endif

using namespace std;

#define all(c) (c).begin(), (c).end()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); it++)
#define rep(i, N) for(int i = 0; i < (N); i++)
#define rep1(i, N) for(int i = 1; i <= (N); i++)
#define rep2(i, s, e) for(int i = (s); i <= (e); i++)
#define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back


#ifdef DEBUG
    #define debug(x...) {dbg::depth++; string dbg_vals = dbg::to_string(x); dbg::depth--; dbg::fprint(__func__, __LINE__, #x, dbg_vals);}
    #define light_debug(x) {dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << "  " << #x << " = " << x << endl; dbg::light = 0;}
#else
    #define debug(x...)
    #define light_debug(x) 
#endif

template<typename T>
T& ckmin(T& a, T b){ return a = a > b ? b : a; }

template<typename T>
T& ckmax(T& a, T b){ return a = a < b ? b : a; }

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

namespace ioUtils {

    char vector_delimiter = ' ';

    template<typename T>
    istream& operator >>(istream&, vector<T>&);

    template<typename... Ts>
    istream& operator >>(istream& is, pair<Ts...>& p){
        is >> p.first >> p.second;
        return is;
    }

    template<typename T> 
    istream& operator >>(istream& is, vector<T>& v){
        for(auto& e : v) is >> e;
	       return is;
    }

    template<typename T>
    ostream& operator <<(ostream&, vector<T>&);

    template<typename... Ts>
    ostream& operator <<(ostream& os, pair<Ts...>& p){
        os << p.first << " " << p.second;
        return os;
    }

    template<typename T>
    ostream& operator <<(ostream& os, vector<T>& v){
        for(auto&& e : v) os << e << vector_delimiter;
        return os;   
    }   
}

using namespace ioUtils;


signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    #ifdef DEBUG
        freopen("debug", "w", stderr);
    #endif
    
    int N;
    cin >> N;
    vi h(N);
    cin >> h;
    vi dp(N);
    dp[N - 2] = abs(h[N - 1] - h[N - 2]);
    rep3(i, N - 3, 0, -1)
    	dp[i] = min(abs(h[i] - h[i + 1]) + dp[i + 1], abs(h[i] - h[i + 2]) + dp[i + 2]);
    cout << dp[0] << '\n';

    #ifdef DEBUG
        dbg::dout << "\nExecution time: " << clock() << "ms\n";
    #endif

    return 0;
}


Measured memory_bytes: 3952
import collections,bisect
N,M=map(int,input().split())
PY=[list(map(int,input().split())) for i in range(M)]
x=collections.defaultdict(list)
for city,year in sorted(PY):
    x[city]+=[year]
for city,year in PY:
    num=bisect.bisect(x[city],year)
    print("%06d%06d"%(city,num))

Measured memory_bytes: 43332
N = int(input())
S = [input() for _ in range(N)]

if N == 1:
    print(S[0].count("AB"))
    quit()

ba, ab, a, b = 0, 0, 0, 0
for s in S:
    if s[0] == "B" and s[-1] == "A":
        ba += 1
    elif s[0] == "B":
        b += 1
    elif s[-1] == "A":
        a += 1
    ab += s.count("AB")

if ba == 0:
    print(ab + min(a, b))
    quit()

ans = ab + ba - 1
if a >= 1:
    ans += 1
    a -= 1
if b >= 1:
    ans += 1
    b -= 1
ans += min(a, b)
print(ans)

Measured memory_bytes: 45656
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<vector<int>> A(N, vector<int>(N, -1));
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        for (int j = 0; j < a; j++) {
            int x, y;
            cin >> x >> y;
            x--;
            A[i][x] = y;
        }
    }

    int ans = 0;
    for (int i = 1; i < (1 << N); i++) {
        int n = i;
        vector<int> result(N, -1);
        int cnt = 0;
        for (int j = 0; j < N; j++) {
            if (n % 2 == 1)
                cnt++;
            result[j] = n % 2;
            n /= 2;
        }

        bool ok = true;
        for (int j = 0; j < N; j++) {
            if (result[j] == 0)
                continue;

            for (int k = 0; k < N; k++) {
                if (A[j][k] == -1)
                    continue;
                else if (A[j][k] != result[k]) {
                    ok = false;
                    break;
                }
            }
        }

        if (ok) {
            ans = max(ans, cnt);
        }
    }
    cout << ans << endl;
}


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

# define C continue;
# define R return

# define D double
# define I insert
# define ll long long
# define ld long double

# define ull unsigned long long
# define ui unsigned int

# define pb push_back
# define pf push_front

# define vi vector < int >
# define vc vector < char >
# define vs vector < string >
# define vb vector < bool >
# define vd vector < D >
# define vll vector < ll >
# define vull vector < ull >
# define vld vector < ld >

# define vvi vector < vector < int > >
# define vvb vector < vector < bool > >
# define vvc vector < vector < char > >
# define vvll vector < vector < ll > >
# define vvd vector < vector < D > >
# define vvld vector < vector < ld > >

# define all(v) (v).begin() , (v).end()
# define allrev(v) (v).rbegin() , (v).rend()
# define allcomp(v) v.begin() , v.end() , comp
# define allrevcomp(v) v.rbegin() , v.rend() , comp

# define pii pair < int , int >
# define pll pair < ll , ll >
# define pld pair < ld , ld >
# define pDD pair < D , D >

# define vpld vector < pld >
# define vpii vector < pii >
# define vpll vector < pll >
# define vpDD vector < pDD >

# define vvpii vector < vector < pii > >
# define F first
# define S second
# define mp make_pair

# define dist(a,b,p,q) sqrt((p-a)*(p-a) + (q-b)*(q-b))

# define pp(n) printf("%.10Lf",n);
# define line cout<<"\n";
# define fast ios_base::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0);

string vow = "aeiou";

const int dxhorse[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dyhorse[] = {1, -1, 2, -2, 2, -2, 1, -1};

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

const ld pie = 3.14159265358979 ;
const ll mod = 1e9 + 7 ;

void solve ( int test_case )
{
    ll a , b ;
    cin >> a >> b ;

    ll ans = a / __gcd ( a , b ) ;
    ans *= b ;

    cout << ans ; line // lcm
}

int main()
{
    int t = 1;
    // cin >> t;

    for ( int i=0 ; i < t ; i++ ) solve(i);
    return 0;
}


Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author champon
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>
#define ok cout << "ok" << endl;
#define sp << " " <<
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const ll inf = 9e18;
template<typename T1, typename T2> ll ceill(T1 a, T2 b){ return (a+b-1)/b; }
void ans(bool b, ostream& out=cout){ out << (b ? "Yes" : "No") << endl; }
void ans2(bool b, ostream& out=cout){ out << (b ? "YES" : "NO") << endl; }
template<typename T> inline bool chmax(T &a, T b){ if(a<b){a=b; return true;} return false; }
template<typename T> inline bool chmin(T &a, T b){ if(a>b){a=b; return true;} return false; }
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val){ fill((T*)array, (T*)(array+N), val); }
int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, -1, 1};

#ifndef INCLUDE_DEBUG_HPP
#define INCLUDE_DEBUG_HPP

#include <iostream>
#include <vector>
#include <map>
using namespace std;

class debug
{
public:
    typedef long long ll;
    template<typename T> void vd(vector<T> vec);
    template<typename T> void vd2(vector<vector<T>> vec);
    template<typename T> void ad(T *arr, ll n);
    template<typename T, size_t N> void ad2(T (&arr)[N], ll n);
    template<typename T> void md(T mp);
};

#endif //INCLUDE_DEBUG_HPP

template<typename T> void debug::vd(vector<T> vec)
{
    for(auto vv : vec) cout << vv << " ";
    cout << endl;
}

template<typename T> void debug::vd2(vector<vector<T>> vec)
{
    for(auto vv : vec) for(auto vvv : vv) cout << vvv << " ";
    cout << endl;
}

template<typename T> void debug::ad(T *arr, ll n)
{
    for(int i=0; i<=n; i++) cout << arr[i] << " ";
    cout << endl;
}

template<typename T, size_t N> void debug::ad2(T (&arr)[N], ll n)
{
    for(int i=0; i<=N; i++) for(int j=0; j<=n; j++) cout << arr[i][j] << " ";
    cout << endl;
}

template<typename T> void debug::md(T mp)
{
    cout << "key : value" << endl;
    for(auto const& m : mp) cout << m.first << " : " << m.second << endl;
    cout << endl;
}
debug debug;

class BPapersPlease {
public:
	void solve(std::istream& in, std::ostream& out)
	{
	    int n;
	    in >> n;
	    vector<int> a(n);
	    for(int i=0; i<n; i++){
	        in >> a[i];
	    }

	    bool flg = true;
	    for(int i=0; i<n; i++){
	        if(a[i]%2 == 0){
	            if(a[i]%3 != 0 && a[i]%5 != 0) flg = false;
	        }
	    }

	    if(flg) out << "APPROVED" << endl;
	    else out << "DENIED" << endl;
	}
};


int main() {
	BPapersPlease solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

int n;
string s;

int main(){
	cin>>n>>s;
	int res=0;
	for(int i=0;i<1000;i++){
		int a[3]={i/100,i/10%10,i%10},I=0;
		for(int j=0;j<n;j++){
			if(I<3&&a[I]==s[j]-'0') I++;
		}
		if(I==3) res++;
	}
	cout<<res<<endl;
}

Measured memory_bytes: 384
#!/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
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
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
inf = float('INF')

#A
def A():
    n, k = LI()
    if n % k:
        print(1)
    else:
        print(0)
    return

#B
def B():
    n = II()
    dp = [0] * (100 + 1)
    dp[4] = 1
    dp[7] = 1
    for i in range(8,n + 1):
        if dp[i - 4] or dp[i - 7]:
            dp[i] = 1
    print(["No", "Yes"][dp[n]])
    return

#C
def C():
    return

#D
def D():
    return

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


Measured memory_bytes: 38512
#include <stdio.h>

int main(){

 unsigned int a,b,A,B;
 while(scanf("%d %d",&A,&B) != EOF){
  a=(A>B)?A:B;
  b=(A<B)?A:B;
  int r;
  while((r=a%b)!=0){
   a=b;
   b=r;
  }
  printf("%d %d\n",b,A/b*B);
 }
 return 0;
}

Measured memory_bytes: 596
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;


typedef long long i64;
const int inf = (int)1.05e9;


int main()
{
	int n;
	vector<int> as, bs;

	scanf("%d", &n);
	as.resize(n);
	bs.resize(n);
	for(int i = 0; i < n; ++i)
		scanf("%d", &as[i]);
	for(int i = 0; i < n; ++i)
		scanf("%d", &bs[i]);

	i64 ans = (1LL << 51) - 1;

	vector<vector<bool>> ok;

	ok.resize(51);
	for(auto& v : ok)
		v.resize(51, false);

	for(int bit = 50; bit >= 0; --bit) {

		i64 ds = (ans) ^ (1LL << bit);

		for(auto& v : ok)
			fill(v.begin(), v.end(), false);
		for(int i = 0; i <= 50; ++i)
			ok[i][i] = true;

		for(int b = 0; b <= 50; ++b) {
			for(int a = 0; a <= 50; ++a) {

				for(int k = 1; k <= 51; ++k) {

					if((ds & (1LL << (k - 1))) == 0)
						continue;
					if(ok[a][b % k]) {
						ok[a][b] = true;
						//printf("[%lld] %d -> %d -> %d\n", ds, a, b % k, b);
						break;
					}
				}
			}
		}

		bool all_ok = true;
		for(int i = 0; i < n; ++i)
			all_ok = all_ok && ok[bs[i]][as[i]];

		//printf("ok: %s\n", all_ok ? "y" : "n");

		if(all_ok)
			ans = ds;
	}

	if(ans & (1LL << 50))
		ans = -1;
	else
		ans = ans * 2;

	printf("%lld\n", ans);

	return 0;
}

/* waffle */


Measured memory_bytes: 256
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def solve(N, A):

    def sad(x):
        s = 0
        for i in range(N):
            s += abs(A[i] - (x + i + 1))
        return s

    min_n = np.min(A) - 10**9
    max_n = np.max(A) + 10**9

    while max_n - min_n != 1:
        tn = (min_n + max_n) // 2
        if sad(tn) < sad(tn + 1):
            max_n = tn
        else:
            min_n = tn

    return sad(max_n)


def main():

    N = in_n()
    A = np.array(readline().split(), np.int64)

    print(solve(N, A))


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', '(i8,i8[:],)')(solve)
    cc.compile()


if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    from my_module import solve
    main()


Measured memory_bytes: 40656
package main

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

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)
	max := 100000

	q := nextInt()
	// primes
	isPrime := make([]bool, max+1)
	for i := 2; i <= max; i++ {
		isPrime[i] = true
	}
	for i := 2; i <= max; i++ {
		if !isPrime[i] {
			continue
		}
		for j := i * 2; j < max; j += i {
			isPrime[j] = false
		}
	}

	// 2017-like
	likes := make([]int, max)
	for i := 3; i < max; i += 2 {
		if isPrime[i] && isPrime[(i+1)/2] {
			likes[i] = 1
		}
	}

	// sums
	sums := make([]int, max+1)
	for i := 3; i < max; i++ {
		sums[i+1] = sums[i] + likes[i]
	}

	w := bufio.NewWriter(os.Stdout)
	for i := 0; i < q; i++ {
		l, r := nextInt(), nextInt()
		fmt.Fprintln(w, sums[r+1] - sums[l])
	}

	w.Flush()
}


Measured memory_bytes: 5120
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappop, heappush, heappushpop

X,Y,Z = map(int,readline().split())
m = map(int,read().split())
ABC = sorted(zip(m,m,m), key = lambda x: x[1] - x[0])

# 手前は A or C, 後半はB or Cでとるようにする

# A or Cで、AをX個とるルール
AC = [0] * (X+Y+Z)
q = [] # a -> cと変更する利点をマイナスで格納する
S = 0
for i,(a,b,c) in enumerate(ABC):
    S += a
    d = a - c
    if len(q) < X:
        heappush(q,d)
    else:
        S -= heappushpop(q,d)
    AC[i] = S

# B or Cで、BをY個とるルール
BC = [0] * (X+Y+Z)
q = [] # b -> cと変更する利点をマイナスで格納する
S = 0
for i,(a,b,c) in enumerate(ABC[::-1]):
    S += b
    d = b - c
    if len(q) < Y:
        heappush(q,d)
    else:
        S -= heappushpop(q,d)
    BC[i] = S
BC = BC[::-1]

answer = max(x+y for x,y in zip(AC[X-1:X+Z],BC[X:]))
print(answer)

Measured memory_bytes: 37200
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

int main(void) {
  int i,j;
  int n,m;
  cin>>n>>m;
  vi x,y;
  rep(i,m){
    int a,b;
    cin>>a>>b;
    if(a==1)x.push_back(b);
    else if(a==n)y.push_back(b);
    else if(b==1)x.push_back(a);
    else if(b==n)y.push_back(a);
  }
  if(x.size()&&y.size()){
    sort(all(x));
    sort(all(y));
    rep(i,x.size()){
      int t=lower_bound(all(y),x[i])-y.begin();
      if(x[i]==y[t]){
	cout<<"POSSIBLE"<<endl;
	return 0;
      }
    }
  }
  cout<<"IMPOSSIBLE"<<endl;
}


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

#define PI 3.14159265359

int main() {
  int A, B, X;
  int i;
  double th;
  
  scanf ("%d %d %d", &A, &B, &X);
  
  
  
  if (X<A*A*B/2) {
  	th = 90 - atan(2.0*X/(1.0*A*B*B)) * 180 / PI;
  }
  else {
  	th = atan (2*(1.0*A*A*B-X)/(1.0*A*A*A) ) * 180 / PI;
  }
  
  
  printf("%lf", th);
  return 0;
}




Measured memory_bytes: 128
import java.util.*;
 
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
 
        int K = sc.nextInt();
        Queue<Long> q = new ArrayDeque<Long>();
 
        for(int i=1; i<=9; i++){
            q.add((long)i);
        }
        for(int i=1; i<=K; i++){
            long x = q.poll();

            if(x%10!=0) q.add(10 * x + x % 10 - 1);
            q.add(10 * x + x % 10);
            if(x%10!=9) q.add(10 * x + x % 10 + 1);
            
            if(i==K){
                System.out.println(x);
            }
        }
    }
}

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

#define LL long long
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()
const int IINF = 1e9;
const LL LINF = 1e18;
const LL mod = 1e9+7;

int main() {
    int N;
    cin >> N;
    int sum = 0;
    int mx = 0;
    REP(i, N) {
        int p;
        cin >> p;
        mx = max(p, mx);
        sum += p;
    }
    int res = sum - mx/2;
    cout << res << endl;
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define X first
#define Y second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
template<class T> using vv=vector<vector<T>>;
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=1e9+7;

int N;
int A[114514];

int main() {
  scanf("%d", &N);

  int mx = -1;
  int mn = N+1;
  rep(i, N) {
    scanf("%d", &A[i]);
    MX(mx, A[i]);
    MN(mn, A[i]);
  }

  if (mx - mn > 1) {
    puts("No");
    return 0;
  }

  int lim = mx+1;
  if (mn == mx) lim++;

  reps(c, mx, lim) {
    int iso = 0;
    int dup = 0;
    rep(i, N) {
      if (A[i] == c) {
        dup++;
      } else {
        assert(A[i] == c-1);
        iso++;
      }
    }
    assert(dup + iso == N);

    if (iso + !!dup > c) continue;
    if (c > iso + dup/2) continue;

    puts("Yes");
    return 0;
  }
  puts("No");
}


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

template <typename T> T gcd(T x, T y) {
  if (y == 0)
    return x;
  return gcd(y, x % y);
}

template <typename T> T lcm(T x, T y) {
  if (x == 0 || y == 0)
    return 0;
  return x / gcd(x, y) * y;
}

int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}

vector<int> p;
vector<int> r;

void init(int n) {
  p.reserve(n);
  r.reserve(n);
  for (int i = 0; i < n; i++) {
    p[i] = i;
    r[i] = 0;
  }
}

int root(int x) { return p[x] == x ? x : p[x] = root(p[x]); }

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

void unite(int x, int y) {
  x = root(x);
  y = root(y);
  if (x == y)
    return;

  if (r[x] < r[y])
    p[x] = y;
  else {
    p[y] = x;
    if (r[x] == r[y])
      r[x]++;
  }
}

int main() {
  int H, W;
  cin >> H >> W;
  vector<string> a(H);
  for (int i = 0; i < H; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < H; i++) {
    bool res = true;
    for (int j = 0; j < W; j++) {
      if (a[i][j] == '#') {
        res = false;
        break;
      }
    }
    if (res) {
      for (int j = 0; j < W; j++) {
        a[i][j] = ' ';
      }
    }
  }
  for (int i = 0; i < W; i++) {
    bool res = true;
    for (int j = 0; j < H; j++) {
      if (a[j][i] == '#') {
        res = false;
        break;
      }
    }
    if (res) {
      for (int j = 0; j < H; j++) {
        a[j][i] = ' ';
      }
    }
  }
  for (int i = 0; i < H; i++) {
    bool res = false;
    for (int j = 0; j < W; j++) {
      if (a[i][j] != ' ') {
        cout << a[i][j];
        res = true;
      }
    }
    if (res)
      cout << endl;
  }
}

Measured memory_bytes: 256
N,M = map(int, input().split())
datas = [list(map(int,input().split())) for i in range(M)]

left = 1
right = N+1
for i in range(M):
  left = max(left, datas[i][0])
  right = min(right, datas[i][1])

ans = max(0, right-left+1)
print(ans)

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

int main() {
    int N;
    cin >> N;
    long A[100];
    long result = 0;
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }
    for(int i = 0; i < N; i++) {
        for(int j = i + 1; j < N; j++) {
        long tmp = abs(A[i] - A[j]);
        if(tmp > result) {
            result = tmp;
        }
        }
    }
    cout << result << endl;
}

Measured memory_bytes: 256
S = input()
N = len(S)


def check(T):
    M = len(T)
    for m in range(M):
        if T[m] not in "ATCG":
            return False
    return True


ans = 0
for i in range(N):
    for j in range(i + 1, N + 1):
        T = S[i:j]
        if check(T):
            ans = max(ans, len(T))
print(ans)


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




//-----------------------------------------------------------------------------------
int N;
double A[101010];
map<double, vector<int>> m;
int ans[101010];
//-----------------------------------------------------------------------------------
int main() {
	cin >> N;
	rep(i, 0, N) scanf("%f", &A[i]);
	rep(i, 0, N) m[A[i]].push_back(i);
	sort(A, A + N);

	for (auto p : m) {
		double i = p.first;
		auto v = p.second;

		int lose = A + N - upper_bound(A, A + N, i);
		int even = v.size() - 1;
		int win = N - 1 - lose - even;

		int score = win * 3 + even;
		for (int j : v) ans[j] = score;
	}

	rep(i, 0, N) printf("%d\n", ans[i]);
}

Measured memory_bytes: 5184
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <utility>
#include <algorithm>
#include <cmath>
#include <climits>
#include <iomanip>
#include <queue>
#include <stack>

using namespace std;

typedef long long ll;

int main() {
    ll n, m, x;    cin >> n >> m >> x;
    ll *c = new ll[n];
    ll **a = new ll*[n];
    for (int i = 0; i < n; i++) {
        a[i] = new ll[m];
        cin >> c[i];
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    }

    ll ans = LLONG_MAX;

    for (int bit = 0; bit < (1<<n); bit++) {
        vector<int> s;
        for (int i = 0; i < n; i++) {
            if (bit & (1<<i))
                s.push_back(i);
        }

        ll tmp = 0;
        vector<ll> score(m, 0);
        bool flag = true;
        for (int i = 0; i < s.size(); i++) {
            int j = s[i];
            tmp += c[j];
            for (int k = 0; k < m; k++)
                score[k] += a[j][k];
        }

        for (int k = 0; k < m; k++) {
            if (score[k] < x)
                flag = false;
        }
        if (flag)
            ans = min(ans, tmp);
    }

    if (ans == LLONG_MAX)
        cout << -1 << endl;
    else 
        cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3632
n = int(input())
lis = []
for i in range(n):
  a = list(map(int,input().split()))
  if a[2] != 0:lis.append(a)
if len(lis) == 1:
  print(lis[0][0],lis[0][1],lis[0][2])
  exit()
for x in range(101):
  for y in range(101):
    co = abs(x -lis[0][0])+abs(y -lis[0][1])+lis[0][2]
    for j in range(1,len(lis)):
      if co != abs(x -lis[j][0])+abs(y -lis[j][1])+lis[j][2]:
        break
      if j == len(lis)-1:
        print(x,y,co)
        exit()


Measured memory_bytes: 3064
import java.io.PrintWriter

fun main(args: Array<String>) {
    PrintWriter(System.out).use { out ->
        solve(out)
        out.flush()
    }
}

fun solve(out: PrintWriter) {
    val n = readInteger()
    var preT = 0
    var preX = 0
    var preY = 0

    repeat(n) {
        val (t, x, y) = readIntegerList()
        if (t - preT < Math.abs(x - preX) + Math.abs(y - preY)) {
            println("No")
            return
        }

        if ((Math.abs(x - preX) + Math.abs(y - preY) - (t - preT)) % 2 != 0) {
            println("No")
            return
        }

        preT = t
        preX = x
        preY = y
    }

    println("Yes")
}

fun readInteger() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntegerList() = readStringList().map(String::toInt)
fun readLongList() = readStringList().map(String::toLong)
fun readDoubleList() = readStringList().map(String::toDouble)


Measured memory_bytes: 51996
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define rc(s) return cout<<s,0
#define pi pair <int, int>
#define sz(x) (int)((x).size())
#define int long long
#define dp down
#define dp1 up

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

const ll inf = 0x3f3f3f3f3f3f3f;
//const ll mod = 1e9 + 7;
const int N = 2e5 + 11;
const int NMAX = 1e4 + 11;
const ll INF64 = 3e18 + 1;
const double lil = 0.0000000000001;

//ifstream cin ("test.in");
//ofstream cout ("test.out");

int n, mod, down[N], up[N];

vector<int>v[N];


void dfs1(int nod, int p){

    ll cur = 1;

    for(auto it : v[nod]){
        if(it == p)continue;
        dfs1(it, nod);
        cur = ((cur*(down[it] + 1))%mod + mod)%mod;
    }

    down[nod] = cur;
}

void dfs2(int nod, int p){

    auto pos = find(all(v[nod]),p);
    if(pos != v[nod].end())v[nod].erase(pos);

    if(sz(v[nod]) >= 1){
            
        int len = sz(v[nod]);

        vector<int>L(len + 5, 0);
        vector<int>R(len + 5, 0);
        

        L[0] = 1;
        for(int i = 1; i < len; i++){
            L[i] = L[i - 1]*(down[v[nod][i - 1]] + 1)%mod;
        }

        R[len - 1] = 1;
        for(int i = len - 2; i >= 0; i--){
            R[i] = R[i + 1]*(down[v[nod][i + 1]] + 1)%mod;
        }

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

            int it = v[nod][i];

            up[it] = (up[nod] + 1)*L[i]%mod*R[i]%mod;

            dfs2(it,nod);
        }
    }


}

void dfs(int nd, int parent)
{
  auto I = find(v[nd].begin(), v[nd].end(), parent);
  if (I != v[nd].end()) v[nd].erase(I);

  if((int)v[nd].size() >= 1)
  {
    int n= v[nd].size();
    vector<ll> L(n, 0) , R(n, 0);
    L[0] = 1;
    R[n-1] = 1;
    for(int i=1; i<n; i++)
      L[i] = L[i-1] * (dp[v[nd][i-1]]+1) %mod;
    for(int i=n-2; i>=0; i--)
      R[i] = R[i+1] * (dp[v[nd][i+1]]+1) % mod;

    for(int i=0; i<n; i++)
    {
      int y = v[nd][i];
      dp1[y] = (dp1[nd] +1) * L[i]%mod*R[i]%mod;
      dfs(y, nd);
    }
  }
}

int32_t main(){
ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();

    cin >> n >> mod;

    for(int i = 1,x,y; i < n; i++){
        cin >> x >> y;
        v[x].pb(y);
        v[y].pb(x);
    }

    dfs1(1,0);

    dfs2(1,0);

    for(int i = 1; i <= n; i++){
        cout << ((down[i]*(up[i] + 1))%mod + mod)%mod << '\n';
    }


}

Measured memory_bytes: 26112
#include <bits/stdc++.h>
using namespace std;
 
const long long INF = 4000000000;
 
long long d[300][300];
 
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> d[i][j];
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i == j) continue;
            for (int k = 0; k < n; k++)
            {
                if (i == k || j == k) continue;
 
                if (d[i][j] + d[i][k] < d[j][k]) {
                    cout << -1 << endl;
                    return 0;
                }
            }
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i == j) continue;
            for (int k = 0; k < n; k++)
            {
                if (i == k || j == k) continue;
 
                if (d[i][j] + d[i][k] <= d[j][k]) {
                    d[j][k] = INF;
                }
            }
        }
    }
 
    long long ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (d[i][j] == INF) continue;
 
            ans += d[i][j];
            d[j][i] = 0;
        }
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 896
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String {
            bytes
                .by_ref()
                .map(|r| r.unwrap() as char)
                .skip_while(|c| c.is_whitespace())
                .take_while(|c| !c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
    input!{
        n: usize,
        k: usize,
        v: [usize; n]
    }
    println!("{}", v.into_iter().filter(|&x| x >= k).count());
}


Measured memory_bytes: 4352
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N = int(input())

points = {}

for _ in range(N):
    c = input()

    if c in points:
        points[c] += 1
    else:
        points[c] = 1

M = int(input())

for _ in range(M):
    c = input()

    if c in points:
        points[c] -= 1
    else:
        points[c] = -1

ans = 0

# print(points)

for v in points.values():
    if ans < v:
        ans = v

if ans < 0:
    ans = 0

print(ans)


Measured memory_bytes: 3064
attrs = Array.new
while line = $stdin.gets
  attrs << line.chomp.split
end

N = attrs[0][0].to_i
M = attrs[0][1].to_i
Q = attrs[0][2].to_i
a = Array.new(N)
b = Array.new(N)
c = Array.new(N)
d = Array.new(N)
Q.times do |i|
  a[i] = attrs[i+1][0].to_i
  b[i] = attrs[i+1][1].to_i
  c[i] = attrs[i+1][2].to_i
  d[i] = attrs[i+1][3].to_i
end
max = 0
[*1..M].repeated_combination(N).to_a.each_with_index do |z, index|
  res = 0
  Q.times do |i|
    if z[b[i]-1] - z[a[i]-1] == c[i]
      res += d[i]
    end
  end
  max = res if max < res
end
puts max

Measured memory_bytes: 28000
#include<stdio.h>

int main(){
	int a,b,d,r;
	scanf("%d %d",&a,&b);
	d=a/b;
	r=a%b;
	double x,y,f;
	x=a;
	y=b;
	f=x/y;
	printf("%d %d %lf\n",d,r,f);
	
return 0;
}


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

public class Main {
    private void solve() {
        String s = sc.next();

        boolean ans = s.charAt(2) == s.charAt(3) && s.charAt(4) == s.charAt(5);
        out.println(ans ? "Yes" : "No");
    }

    private static PrintWriter out;
    private static MyScanner sc;

    private static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        private MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

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

    public static void main(String[] args) {
        out = new PrintWriter(new BufferedOutputStream(System.out));
        sc = new MyScanner();
        new Main().solve();
        out.close();
    }
}


Measured memory_bytes: 22996
#include<bits/stdc++.h>
using namespace std;
int N,K;
vector<int> book[10];
int memo[10][2001];
int value(int shu,int n){
  if(n==0) return 0;
  int sum=0;
  for(int i=0;i<n;i++){
    sum+=book[shu][i];
  }
  return sum+(n-1)*n;
}

int solve(int shu,int n){
  if(shu==10){
    return 0;
  }
  if(memo[shu][n]!=-1) return memo[shu][n];
  int ret=0;
  for(int i=0;i<=book[shu].size();i++){
    if(n+i>K) break;
    ret=max(ret,solve(shu+1,n+i)+value(shu,i));
  }
  return memo[shu][n]=ret;	    
}
int main(){  
  cin>>N>>K;
  for(int i=0;i<N;i++){
    int c,g;
    cin>>c>>g;
    book[g-1].push_back(c);
  }
  for(int i=0;i<10;i++){
    sort(book[i].begin(),book[i].end(), greater<int>() );
  }
  for(int i=0;i<10;i++){
    for(int j=0;j<2000;j++){
      memo[i][j]=-1;
    }
  }

  cout<<solve(0,0)<<endl;
  return 0;
}

Measured memory_bytes: 1312
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int h = sc.nextInt();
    int w = sc.nextInt();
    int[][] a = new int[h][w];
    List<String> list = new ArrayList<>();
    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++)a[i][j]=sc.nextInt();
    for(int i=0;i<h;i++)
      for(int j=0;j<w-1;j++)
        if(a[i][j]%2==1){
          a[i][j]--;
          a[i][j+1]++;
          list.add((i+1)+" "+(j+1)+" "+(i+1)+" "+(j+2));
        }
    for(int i=0;i<h-1;i++)
      if(a[i][w-1]%2==1){
        a[i][w-1]--;
        a[i+1][w-1]++;
        list.add((i+1)+" "+w+" "+(i+2)+" "+w);
      }
    System.out.println(list.size());
    for(String s:list)System.out.println(s);
  }
}

Measured memory_bytes: 100076
n,t,e=map(int,input().split())
a=list(map(int,input().split()))
tmp=0
for i in range(n):
    x=(t-e-1)//a[i]
    if (x+1)*a[i]<=t+e:
        print(i+1)
        break
else :
    print(-1)


Measured memory_bytes: 5596
N, M = map(int, input().split())
penalty = {key: 0 for key in range(N+1)}
accept = {key: 0 for key in range(N+1)}
ac = 0
wa = 0

for i in range(M):
    tmp = list(input().split())
    if tmp[1] == 'WA':
        if accept[int(tmp[0])] == 0:
            penalty[int(tmp[0])] += 1
    else:
        if accept[int(tmp[0])] != 1:
            accept[int(tmp[0])] = 1
            ac += 1

for k, v in penalty.items():
    if accept[k] == 1:
        wa += v

print(ac, wa)


Measured memory_bytes: 27368
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <map>
#include <utility>
#include <iomanip>

using namespace std;

#define ll long long

void solve()
{
    ll X, A;
    cin >> X >> A;
    cout << ((X < A) ? 0 : 10) << endl;
}

int main()
{
    solve();
    return 0;
}


Measured memory_bytes: 256
from heapq import heapify, heappop

N, M = map(int, input().split())
As = [(A, i) for i, A in enumerate(map(int, input().split()))]

if 2 * (N - M - 1) > N:
    print('Impossible')
    exit()
elif N - M == 1:
    print(0)
    exit()


def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    x = find(x)
    y = find(y)
    if x == y: return
    if rank[x] < rank[y]:
        parent[x] = y
    else:
        parent[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


parent = [i for i in range(N)]
rank = [0] * N

for i in range(M):
    x, y = map(int, input().split())
    union(x, y)

for i in range(N):
    find(i)

# 各々の木の中で、最小のaiを持つ頂点iを求める（辺の追加時に使用する）
minAs = {}
for A, i in As:
    p = parent[i]
    minAs[p] = min(minAs.get(p, (float('inf'), 0)), (A, i))

done = [False] * N
ans = 0
for (A, i) in minAs.values():
    done[i] = True
    ans += A

# 残りの頂点のうち、aiが小さい方から、(N - M - 2)個を選ぶ
heapify(As)
rest = N - M - 2
while rest > 0:
    A, i = heappop(As)
    if not done[i]:
        ans += A
        rest -= 1

print(ans)


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

int main(){
    int N;
    cin >> N;
    set<char> set;
    for(int i=0;i<N;i++){
        char x;
        cin >> x;
        set.insert(x);
    }
    if(set.size()==3) cout << "Three" << endl;
    else cout << "Four" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define V vector
#define VI vector<int>
#define VVI vector<vector<int>>
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define MOD 1000000007
#define INF 1e9
#define F first
#define S second
#define All(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;

int main(void){
    int a,b;
    cin>>a>>b;
    if(a<=0&&b>=0)cout<<"Zero"<<endl;
    else if(a>0||(a-b+1)%2==0)cout<<"Positive"<<endl;
    else cout<<"Negative"<<endl;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
   int a; cin>>a; double s=0;
   double d[a];
  rep(i,a) cin>>d[i];
  rep(i,a) s=s+1/d[i];
  cout<<1/s<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <iomanip>
#include <stack>
#include <bitset>
#include <map>

using namespace std;
typedef long long ll;
const ll INF = 1LL << 50;

int solve();

int main(void) {
	//FILE *fpin = freopen("data.txt", "r", stdin);
	while (solve()) {}
	return 0;
}

int solve() {

	ll N, M;
	cin >> N >> M;

	const int NMAX = 1000;
	const int MMAX = 2000;
	int a[MMAX], b[MMAX];
	ll c[MMAX];

	for (int i = 0; i < M; i++) {
		cin >> a[i] >> b[i] >> c[i];
		c[i] = -c[i];
	}

	ll dist[NMAX];

	for (int i = 0; i < N; i++) {
		dist[i] = INF;
	}

	dist[0] = 0;

	for (int loop = 0; loop < N - 1; loop++) {
		for (int i = 0; i < M; i++) {
			if (dist[a[i] - 1] == INF) continue;
			if (dist[b[i] - 1] > dist[a[i] - 1] + c[i]) {
				dist[b[i] - 1] = dist[a[i] - 1] + c[i];
			}
		}
	}

	ll ans = dist[N - 1];

	bool negative[NMAX];

	for (int i = 0; i < N; i++) {
		negative[i] = false;
	}

	for (int loop = 0; loop < N; loop++) {
		for (int i = 0; i < M; i++) {
			if (dist[a[i] - 1] == INF) continue;
			if (dist[b[i] - 1] > dist[a[i] - 1] + c[i]) {
				dist[b[i] - 1] = dist[a[i] - 1] + c[i];
				negative[b[i] - 1] = true;
			}
			if (negative[a[i] - 1] == true) {
				negative[b[i] - 1] = true;
			}
		}
	}

	if (negative[N - 1])
		cout << "inf" << endl;
	else
		cout << -ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
#define m 1000000007
using namespace std;
int main()
{
    /*string s;
    cin>>s;
    int n=s.size();
    if(s[n-1]=='s')
        s.append("es");
    else
        s.append("s");
    cout<<s<<endl;
        int n;bool c=false;
        cin>>n;
    int a[n],b[n];
    for(int i=0;i<n;i++)
        cin>>a[i]>>b[i];

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

        if(a[i]==b[i] && a[i+1]==b[i+1] && a[i+2]==b[i+2])
            c=true;
    }
    if(c)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;*/


  ll n,ans=0;
  cin>>n;

  for(int i=1;i<=n;i++)
    ans+= (n-1)/i;

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






Measured memory_bytes: 3616
#include<bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vector<int> >
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
using ll = long long;
using ld =long double;
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
typedef pair<int,pii> piii;
#define mp make_pair

int dp[200010][250];
signed main(){
    int n; cin>>n;
    vector<int>t(n);
    vector<int>v(n);
    rep(i,n)cin>>t[i];
    rep(i,n)cin>>v[i];
    rep(i,n-1)t[i+1]+=t[i];
    int allt=2*t[n-1];
    rep(i,200010)rep(j,250)dp[i][j]=-INF;
    int cnt=0;
    dp[0][0]=0;
    rep(i,200010-1){
        if(i>=2*t[cnt]){
            cnt++;
        }
        rep(j,250-1){
            if(j>v[cnt]*2)continue;
            if(dp[i][j]==-INF)continue;
            cmax(dp[i+1][j],dp[i][j]+j);
            if(j+1<=2*v[cnt])
                cmax(dp[i+1][j+1],dp[i][j]+j+1);
            if(j-1>=0)
                cmax(dp[i+1][j-1],dp[i][j]+j-1);
        }
    }
    printf("%.10lf\n",(double)dp[allt][0]/(double)4);
}


Measured memory_bytes: 195584
#include<bits/stdc++.h>
using namespace std;
void bubbleSort(string arr[], int N){
    int i, j;
    for(i=0; i < N-1; i++){
        for(j=N-1; j>i; j--){
            if(arr[j][1] < arr[j-1][1] ) swap(arr[j], arr[j-1]);
        }
    }
    
    for(i =0; i < N; ++i){
        cout << arr[i] << ((i != N-1) ? " " : "");
    }
    cout << endl;
}

void selectionSort(string arr[], int N){
    int i, j;
    for(i=0; i<N-1; i++){
        int minj = i;
        char min_num = arr[i][1];
        for(j=i+1; j < N; ++j){
            if(min_num > arr[j][1]){
                min_num = arr[j][1];
                minj = j;
            }
        }
        swap(arr[minj], arr[i]);
    }
    for(i = 0 ; i < N; ++i){
        cout << arr[i] << ((i != N-1) ? " ": "");
    }
    cout << endl;
}

bool isStable(string arr_in[], string arr_out[], int N){
    int i, j, a, b;
    for(i =0; i < N; ++i){
        for(j=i+1; j<N; ++j){
            for(a=0; a < N; ++a){
                for(b=a+1; b < N ; b++){
                    if(arr_in[i][1] == arr_in[j][1] && arr_in[i] == arr_out[b] && arr_in[j] == arr_out[a]){
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

int main(){
    int N; cin >> N;
    string arr_in[N], arrBubbled[N], arrSelected[N];
    for(int i =0 ;i < N; i++){
        cin >> arr_in[i];
        arrBubbled[i] = arr_in[i];
        arrSelected[i] = arr_in[i];
    }
    
    bubbleSort(arrBubbled, N);
    if(isStable(arr_in, arrBubbled, N)) cout << "Stable" << endl;
    else cout << "Not stable" << endl;
    
    selectionSort(arrSelected, N);
    if(isStable(arr_in, arrSelected, N)) cout << "Stable" << endl;
    else cout << "Not stable" << endl;
    
    return 0;
}


Measured memory_bytes: 3168
#include <iostream>
#include <cstring>

using namespace std;

const int INF = 1000000007;

int main(){
	int n, m;
	int land[200][200];
	int sea[200][200];
	int z[1000];
	while(cin >> n >> m && m){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				land[i][j] = (i==j ? 0 : INF);
				sea[i][j] = (i==j ? 0 : INF);
			}
		}
		for(int i=0;i<m;i++){
			int x, y, t; char s;
			cin >> x >> y >> t >> s;
			--x; --y;
			if(s == 'L') land[x][y] = land[y][x] = t;
			else         sea[x][y] = sea[y][x] = t;
		}
		for(int k=0;k<n;k++){
			for(int i=0;i<n;i++){
				for(int j=0;j<n;j++){
					land[i][j] = min(land[i][j], land[i][k]+land[k][j]);
					sea[i][j] = min(sea[i][j], sea[i][k]+sea[k][j]);
				}
			}
		}
		int cost[2][200];
		for(int i=0;i<n;i++) cost[0][i] = cost[1][i] = INF;
		int R; cin >> R;
		for(int i=0;i<R;i++){
			cin >> z[i];
			--z[i];
		}
		cost[0][z[0]] = 0;
		for(int i=1;i<R;i++){
			int cur = 1-i%2, next = 1-cur;
			for(int j=0;j<n;j++) cost[next][j] = INF;
			for(int j=0;j<n;j++){
				cost[next][j] = min(cost[next][j], cost[cur][j]+land[z[i-1]][z[i]]);
				for(int k=0;k<n;k++){
					int add = min(land[z[i-1]][j] + sea[j][k], INF);
					add = min(add + land[k][z[i]], INF);
					cost[next][k] = min(cost[next][k], cost[cur][j]+add);
				}
			}
		}
		int res = INF;
		for(int i=0;i<n;i++) res = min(res, cost[1-R%2][i]);
		cout << res << endl;
	}
}

Measured memory_bytes: 1476