akhauriyash/Code-Regression huggingface dataset:
/* 
chirag11032000
Chirag Thakur
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using pll = pair < ll, ll >;

template < typename T > using OrderedSet = tree < T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update >;
template < typename T > using MinPriorityQueue = priority_queue < T, vector < T >, greater < T > >;

#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template < typename Arg1 >
void __f(const char* name, Arg1&& arg1) {
	cerr << name << " : " << arg1 << std :: endl;
}
template < typename Arg1, typename... Args >
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');
	cerr.write(names, comma - names) << " : " << arg1 << " | ";
	__f(comma + 1, args...);
}
#else
#define trace(...)
#endif

#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

const db PI = acos(-1);
const ll LINF = LLONG_MAX;
const int INF = INT_MAX, MOD = 1e9 + 7, N = 1e5 + 10;

vector < int > g[N];
bool seen[N];

void testCase();
void dfs(int u);

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	testCase();
	cerr << "Time taken: " << int((clock() * 1000.) / CLOCKS_PER_SEC) << "ms\n";
	return 0;
}

void testCase() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int x, y, z;
		cin >> x >> y >> z;
		g[x].eb(y);
		g[y].eb(x);
	}
	int cc = 0;
	for (int i = 1; i <= n; ++i) {
		if (!seen[i]) {
			dfs(i);
			++cc;
		}
	}
	cout << cc << "\n";
}

void dfs(int u) {
	seen[u] = true;
	for (auto &v: g[u]) {
		if (!seen[v]) {
			dfs(v);
		}
	}
}

Measured memory_bytes: 8960
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define len(x) (int)(x.size())
#define all(vs) vs.begin(), vs.end()
using ii = pair<int, int>;
using ll = long long;

ll dis(ll a, ll b){
	return (a-b)*(a-b);
}
int32_t main(){
	ios::sync_with_stdio(0);	
	int n;
	cin >> n;
	vector<ll> vs(n);
	for(auto &x:vs) cin >> x;
       	ll ans = 1e18;
	for(ll y=1; y<=100; ++y){
		ll res = 0;
		for(auto &x:vs) res+=dis(x, y); 
		ans = min(ans, res);
	}	
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef unsigned long long int ull;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ff first
#define ss second
#define pb push_back
#define Inf  1e18
#define inf -1e18
#define mod 1000000007
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using mll = map<ll,ll>;
using umll = unordered_map<ll,ll>;
using sll = set<ll>;
using msll = multiset<ll>;
using pll = pair<ll,ll>;
 
ll MUL(ll A,ll B){
  return (A%mod*B%mod)%mod;
}
 
ll ADD(ll A,ll B){
  return (A%mod+B%mod)%mod;
}
 
ull power(ll A,ll B) {
    ull RES = 1;
    while (B > 0)
    {
        if (B & 1)
            RES = RES*A;
        B = B>>1;
        A = A*A;
    }
  return RES;
}
 
 

 
void testcases(int cases){
		
			int N;
			cin >> N;
		    if(N%1000==0){
				cout << 0 << endl;
			}
			else{
				int tmp = ((N/1000) + 1)*1000;
				cout << tmp - N << "\n";
			}
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
    ll t;
   // cin >> t;
   t = 1;
    ll Case =1 ;
    while(t--)
    {
      testcases(Case++);
    }
}



Measured memory_bytes: 3640
#ifdef _MSC_VER
#include <__msvc_all_public_headers.hpp>
#undef min
#undef max
#else
#define NDEBUG
#include <bits/stdc++.h>
#endif

using namespace std;
using large = long long;
static constexpr int Max = 10'000'000;
static large table[10'000'005];

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

    table[0] = 0;

    for (auto x = 1; x <= n; ++x)
        table[x] = 1;

    for (auto d = 2; d <= n; ++d) {
        for (auto x = d; x <= n; x += d)
            table[x]++;
    }

    auto mul = 0LL;
    for (auto x = 1LL; x <= n; ++x)
        mul += x * table[x];
    cout << mul << endl;
    return 0;
}


Measured memory_bytes: 81692
a, b, c, x, y = gets.split(" ").map(&:to_i)
sum = 0
z = [x, y].min

if c * 2 < a + b
  sum += z * c * 2
  x -= z
  y -= z
end

puts sum + [a, c * 2].min * x + [b, c * 2].min * y


Measured memory_bytes: 1788
import java.util.*;
public class Main{

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

      for(int i = 0; i < n; i++) {
        arr[i] = sc.nextLong();
      }
      
      long[] leftSum = new long[n];
      for(int i = 0; i < n - 1; i++) {
        if(i == 0) {
          leftSum[i] = arr[i];
        } else {
          leftSum[i] = arr[i] + leftSum[i - 1];
        }
      }

      long[] rightSum = new long[n];
      for(int i = n - 1; i >= 0; i--) {
        if(i == n - 1) {
          rightSum[i] = arr[i];
        } else {
          rightSum[i] = arr[i] + rightSum[i + 1];
        }
      }
      long min = Long.MAX_VALUE;
      for(int i = 0; i < n - 1; i++) {
        min = Math.min(min, Math.abs(leftSum[i] - rightSum[i+1]));
      }
      System.out.println(min);
  }
}


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

int main() {
    int n,s;
  	s = 0;
    cin >> n;
    vector<int> p(n),q(3);

    for (int i = 0; i < n; i++) {
        cin >> p.at(i);
    }

    for (int i = 0; i < n - 2; i++) {
        q.at(0) = p.at(i);
        q.at(1) = p.at(i + 1);
        q.at(2) = p.at(i + 2);
        sort(q.begin(),q.end());
        if (q.at(1) == p.at(i + 1)) {
            s++;
        }
    }

    cout << s << endl;
}

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

int main(){
  string s;
  cin >> s;
  int64_t k;
  cin >> k;
  for(int i=0;i<s.size()-1;i++){
    if('z' + 1 - s.at(i) <= k && s.at(i) != 'a'){
      k -= 'z' + 1 - s.at(i);
      s.at(i) = 'a';
    }
  }
  //cout << k % 26 << ",";
  s.at(s.size()-1) = (s.at(s.size()-1) - 'a' + (k % 26)) % 26 + 'a';
  if(s.at(s.size()-1) > 'z'){
    s.at(s.size()-1) = s.at(s.size()-1) - 26;
  }
  //cout << s.at(s.size()-1) - 0 << endl;
  cout << s << endl;
}
      
    

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
int diff(char c, char base) {
    return (c-base+26)%26;
}
int conv(char c, int d) {
    return (c-d-'a'+26)%26+'a';
}
int main(void){
    string s;
    while(getline(cin, s)) {
        int d;
        rep(i, s.size()) {
            if(i<s.size()-3 &&
                    (diff(s[i], 't') == diff(s[i+1], 'h') &&
                     diff(s[i], 't') == diff(s[i+2], 'i') &&
                     diff(s[i], 't') == diff(s[i+3], 's')) || 
                    (diff(s[i], 't') == diff(s[i+1], 'h') &&
                     diff(s[i], 't') == diff(s[i+2], 'a') &&
                     diff(s[i], 't') == diff(s[i+3], 't'))) {
                d = diff(s[i], 't');
                break;
            }
            if(i<s.size()-2 &&
                    (diff(s[i], 't') == diff(s[i+1], 'h') &&
                     diff(s[i], 't') == diff(s[i+2], 'e'))) {
                d = diff(s[i], 't');
                break;
            }
        }
        rep(i, s.size()) {
            if(s[i] >='a' && s[i]<='z') s[i] = conv(s[i], d);
        }
        cout << s << endl;
    }
}

Measured memory_bytes: 1176
#!/usr/bin/env python3
import sys

MOD = 2019  # type: int


def solve(L: int, R: int):
    list_lr_mod = []
    ans = 2018

    for x in range(L, R + 1):
        list_lr_mod.append(x % MOD)

        if len(list_lr_mod) >= 2019:
            print(0)
            return

    list_lr_mod = list(set(list_lr_mod))

    if 0 in list_lr_mod:
        print(0)
        return

    for i in range(len(list_lr_mod) - 1):
        for j in range(i + 1, len(list_lr_mod)):
            tmp = list_lr_mod[i] * list_lr_mod[j]
            ans = min(ans, tmp % MOD)

    print(ans)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    L = int(next(tokens))  # type: int
    R = int(next(tokens))  # type: int
    solve(L, R)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3188
//TAKOYAKI
import java.util.*;
public class Main{
  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int power[]=new int[n];
    for (int i=0;i<n;i++) {
      power[i]=sc.nextInt();
    }
    int count=0;
    int temp;
    for (int i=0;i<n-1;i++) {
      for (int j=i+1;j<n;j++) {
        temp=power[i]*power[j];
        count=count+temp;
      }
    }
    System.out.println(count);
  }
}


Measured memory_bytes: 23124
#include<stdio.h>
int prime(int x);
int main(void)
{
   int n, t, a=0;
   scanf("%d",&n);
   for(int i=0;i < n;i++)
   {
      scanf("%d",&t);
      a+=prime(t);
   }
   printf("%d\n",a);
}
int prime(int x)
{
   int i;
   if(x == 2) return 1;
   if(x < 2 || x%2==0) return 0;
   i = 3;
   while(i <= sqrt(x))
   {
      if(x%i==0) return 0;
      i+=2;
   }
   return 1;
}


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

int cut;
int n;
char s[100010];
int main(){
	scanf("%d",&n);
	scanf("%s",s+1);
    for(int i=1; i<=n; i++){
    	if(s[i]==s[i-1]){
    		cut++;
		}
	}
	printf("%d",n-cut);
	return 0;
}

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

int main(){
  int ans=0;
  string s;
  cin >> s;
  s += "fffff";
  
  rep(i,3){
    if(s[i] == 'R'){
      ans = max(ans,1);
      if(s[i+1] == 'R'){
        ans = max(ans,2);
        if(s[i+2] == 'R'){
          ans = max(ans,3);
        }
      }
    }
  }
      
  cout << ans;
  
  return 0;
}


Measured memory_bytes: 3620
#include<stdio.h>
#define MAX 100000

int A[MAX],n;

int partition(int p,int r){
  int x,i,j,t;
  x=A[r];
  i=p-1;
  for(j=p;j<r;j++){
    if(A[j]<=x){
      i++;
      t=A[i];
      A[i]=A[j];
      A[j]=t;
    }
  }
  t=A[i+1];
  A[i+1]=A[r];
  A[r]=t;
  return i+1;
}

int main(){
  int i,q;

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

  q=partition(0,n-1);

  for(i=0;i<n;i++){
    if(i) printf(" ");
    if(i == q) printf("[");
    printf("%d",A[i]);
    if(i==q) printf("]");
 }
  printf("\n");
  return 0;
}

Measured memory_bytes: 992
H, W, K = map(int,input().split())

C = [list(input()) for _ in range(H)]

ans = 0
for i in range(2**H):
    for j in range(2**W):
        mm = 0
        for h in range(H):
            for w in range(W):
                if ((i>>h)&1) and ((j>>w)&1) and C[h][w]=="#":
                    mm += 1
        if mm==K:
            ans += 1
            # print(bin(i),bin(j))
print(ans)




Measured memory_bytes: 68500
import java.util.Scanner;

public class Main {

	static Scanner scanner;

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

	    String s=gs();

	    //System.out.print(nr*2*Math.PI);
	    if (s.contains("7")) {
	    	System.out.print("Yes");
	    }else {
	    	System.out.print("No");
	    }


	}

	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}

	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}

Measured memory_bytes: 35772
#!/usr/bin/env python3
import sys


def solve(A: int, B: int, C: int, K: int):

    a = K - A
    if a <= 0:
        print(K)
        return
    b = a - B
    if b <= 0:
        print(A)
        return
    c = b - C
    print(A-b)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(A, B, C, K)

if __name__ == '__main__':
    main()


Measured memory_bytes: 61760
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		double [] x = new double [a];
        double [] y = new double [a];
        for(int i=0;i<a;i++){x[i] = sc.nextDouble();
                             y[i] = sc.nextDouble();
                            }
        double b = 0;
        for(int i=0;i<a-1;i++){
          for(int j=i+1;j<a;j++){
            b+=Math.sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));           
          }                           
        }
        b*=2;
        b/=a;
		System.out.println(b);
	}
}


Measured memory_bytes: 22868
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define FORR(x, arr) for(auto& x:arr)
#define ITR(x, c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;
typedef pair<int, int> P;

string s;

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
    cin >> s;
    bool ok = false;
    FOR(i, 8) {
        string a = s.substr(0, i);
        string b = s.substr(s.size()-(7-i), 7-i);
        if (a+b=="keyence") ok = true;
    }
    cout << (ok ? "YES" : "NO") << endl;
	return 0;
}

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

const int mod = 1e9+7;

long long tree[1000000];
vector<int> lazy;
int n;
vector<long long> dp;
vector<int> beauty, height;

void update(int pos, int ind = 1, int l = 1, int r = n)
{
	if(l == r) {
		tree[ind] = dp[pos];
		return ;
	}
	int mid = (l+r)/2;
	if(pos <= mid) update(pos, 2*ind, l, mid);
	else update(pos, 2*ind+1, mid+1, r);
	tree[ind] = max(tree[2*ind], tree[2*ind+1]);
}

long long query(int ql, int qr, int ind = 1, int l = 1, int r = n)
{
	// printf("ql : %d qr : %d ind : %d l : %d r : %d\n", ql, qr, ind, l, r);
	if(ql > qr) return 0;
	if(l == r) return tree[ind];
	if(l == ql && r == qr) {
		return tree[ind];
	}
	int mid = (l+r)/2;
	return max(query(ql, min(qr, mid), 2*ind, l, mid), query(max(mid+1, ql), qr, 2*ind+1, mid+1, r));
}

int main() 
{
	scanf("%d", &n);
	beauty = vector<int>(n+1);
	height = vector<int>(n+1);
	dp = vector<long long>(n+1);
	for(int i = 0; i < n; i++) {
		scanf("%d", &height[i]);
	}
	for(int i = 0; i < n; i++) {
		scanf("%d", &beauty[i]);
	}
	long long ans = 0;
	for(int i = 0; i < n; i++) {
		long long max_ = query(0, height[i]);
		dp[height[i]] = max_ + beauty[i];
		update(height[i]);
		ans = max(ans, dp[height[i]]);
	}
	printf("%lld\n", ans);
 }

Measured memory_bytes: 10540
#include <bits/stdc++.h>
using namespace std;
int main(){
	int w, h, x, y, r;
	cin >> w >> h >> x >> y >> r;
	if(x-r>=0 && w-r>=x && y-r>=0 && h-r>=y)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}



Measured memory_bytes: 3116
import sys
n = int(input())
t,a = list(map(int, input().split()))
hhh = list(map(int, input().split()))
ttt = [abs((t - h*0.006)-a) for h in hhh]
min_t = min(ttt)
for i in range(n):
  if ttt[i] == min_t:
    print(i+1)
    sys.exit()


Measured memory_bytes: 3060
import sys
input = sys.stdin.readline

A, B = map(int, input().split())
out = 0
if A > B:
    out += A
    A -= 1
else:
    out += B
    B -= 1
if A > B:
    out += A
    A -= 1
else:
    out += B
    B -= 1
print(out)


Measured memory_bytes: 2940
N = int(input())
p = list(map(int, input().split()))

if 0 in p:
  print(0)
  exit()

for i in range(N-1):
  p[i+1] = p[i] * p[i+1]
  if p[i+1] > 10**18:
    print('-1')
    exit()
print(p[i+1])  

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

// Function Macros:
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define setpre(n) cout << fixed << setprecision(n)

// Type / Class / Struct Definitions:
using namespace std;

using ll = long long;
using ull = unsigned long long;

// Constants:
const int INF = (1ll << 30) - 1;  // approx 1.07e9
const ll INFLL = 1ll << 60;       // approx 1.15e18
const int MOD = 1e9 + 7;          // 998244353
const long double EPS = 1.0e-14;

// Global Variables:

// Prototype Declarations:
int gcd(int, int);
template <class T>
inline bool chmin(T&, T);
template <class T>
inline bool chmax(T&, T);

// ================ Main Loop ================
int main() {
    int n;
    cin >> n;
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        ans += (ll)i * (n / i) * (n / i + 1) / 2;
    }
    cout << ans << endl;
    return 0;
}
// ===========================================

// Functions:
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

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;
}


Measured memory_bytes: 3592
import java.util.*;
import java.lang.*;

public class Main{
    int a[] = {3, 0, 1};

    Main(){
	Scanner sc = new Scanner(System.in);
	boolean f = false;
	while(sc.hasNext()){
	    int n = sc.nextInt();
	    if(n == 0) break;
	    if(f) System.out.println();
	    f = true;
	    Vector<Tm> vec = new Vector<Tm>();

	    for(int i = 0; i < n; i++){
		String nm = sc.next();
		int s = 0;
		for(int j = 0; j < 3; j++) s += (a[j]*sc.nextInt());
		vec.add(new Tm(nm, s));
	    }
	    Collections.sort(vec);

	    for(int i = 0; i < vec.size(); i++) (vec.get(i)).print();
	}
    }

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

class Tm implements Comparable<Tm>{
    public String nm;
    public int sc;

    public Tm(){}
    public Tm(String nm, int sc){
	this.nm = nm;
	this.sc = sc;
    }

    public int compareTo(Tm tm){
	if(this.sc > tm.sc) return -1;
	if(this.sc < tm.sc) return 1;
	return 0;
    }

    public void print(){
	System.out.println(nm+","+Integer.toString(sc));
	return ;
    }
}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
#define int long long
const int MOD = 1e9 + 7;
using pii=std::pair<int,int>;
using namespace std;

const int maxn = 1e3 + 5;

int n, a, b, c, d, dp[maxn][maxn], fact[maxn], invfact[maxn];

int mod_expo(int x, int p)
{
    if(!p)
        return 1;
    int res = mod_expo(x, p / 2);
    res *= res;
    res %= MOD;
    if(p & 1)
        res *= x;
    return res % MOD;
}

int mod_inv(int x)
{
    return mod_expo(x, MOD - 2);
}

int nCr_mod(int x, int r)
{
    if(x < r)
        return 0;
    int num = fact[x];
    int invdenom = (invfact[r] * invfact[x - r]) % MOD;
    return (num * invdenom) % MOD;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    fact[0] = invfact[0] = 1;
    for(int i = 1; i < maxn; i++)
    {
        fact[i] = (fact[i - 1] * i) % MOD;
        invfact[i] = mod_inv(fact[i]);
    }
    cin >> n >> a >> b >> c >> d;
    dp[a][n] = 1;
    for(int i = a; i <= b; i++)
        for(int j = n; j >= 0; j--)
            if(dp[i][j])
            {
                dp[i + 1][j] += dp[i][j];
                dp[i + 1][j] %= MOD;
                int ways = fact[j], mult = invfact[i];
                for(int k = 1; k <= d && i * k <= j; k++)
                {
                    ways *= mult;
                    ways %= MOD;
                    int curways = (invfact[j - k * i] * invfact[k]) % MOD;
                    if(k >= c)
                    {
                        dp[i + 1][j - i * k] += dp[i][j] * ((ways * curways) % MOD);
                        dp[i + 1][j - i * k] %= MOD;
                    }
                }
            }
    cout << dp[b + 1][0] << "\n";
    return 0;
}

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

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

struct modint{
    ll a;
    const ll MOD=1e9+7;
    modint(ll a_=0){
        a=a_%MOD;
        if(a<0) a+=MOD;
    }
    modint inv()const{
        ll n=1,m=MOD-2,A=a;
        while(m){
            if(m&1)(n*=A)%=MOD;
            (A*=A)%=MOD;
            m>>=1;
        }
        modint y(n);
        return y;
    }
    bool operator==(const modint& x){
        return a==x.a;
    }
    bool operator!=(const modint& x){
        return a!=x.a;
    }
    modint& operator=(const modint& x){
        a=x.a;
        return *this;
    }
    modint operator+(const modint& x){
        modint y;
        y.a=a+x.a;
        if(y.a>MOD) y.a-=MOD;
        return y;
    }
    modint operator-(const modint& x){
        modint y;
        y.a=a-x.a;
        if(y.a<0) y.a+=MOD;
        return y;
    }
    modint operator*(const modint& x){
        modint y;
        y.a=(a*x.a)%MOD;
        return y;
    }
    modint operator/(const modint& x){
        modint y;
        y.a=(a*x.inv().a)%MOD;
        return y;
    }
    modint& operator+=(const modint& x){
        *this=*this+x;
        return *this;
    }
    modint& operator-=(const modint& x){
        *this=*this-x;
        return *this;
    }
    modint& operator*=(const modint& x){
        *this=*this*x;
        return *this;
    }
    modint& operator/=(const modint& x){
        *this=*this/x;
        return *this;
    }
};
istream& operator>>(istream &in,modint& x){
    ll a_;
    in>>a_;
    modint y(a_);
    x=y;
    return in;
}
ostream& operator<<(ostream &out,const modint& x){
    out<<x.a;
    return out;
}
modint pwr(ll a,ll b){
    modint n(1),A(a);
    while(b){
        if(b&1) n*=A;
        A*=A;
        b>>=1;
    }
    return n;
}

class FSmallProducts {
public:
    void solve(istream& in, ostream& out) {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        int n,k,m;
        in>>n>>k;
        m=(int)sqrt(n);
        vector<modint> c(2*m),s(2*m+1),ns(2*m+1);
        fr(i,m) c[i]=1,c[i+m]=n/(m-i)-n/(m-i+1);
        if(n/m==m) c[m]-=1;
        s[0]=1;
        fr(_,k){
            ifr(i,2*m) ns[i]=ns[i+1]+(s[0]-s[2*m-i])*c[i];
            s.swap(ns);
        }
        out<<s[0]<<endl;
    }
};

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


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

int main(){

    int N;
    cin >> N;
    long int a[N];
    long long int ans = 0;
    for(int i = 0;i<N;i++){
        cin >> a[i];
        ans += a[i];
    }
    
    long long int temp = 0,A;


    for(int i = 0;i<N-1;i++){
        //ans -= a[i];
        temp += a[i];
        
        A = min(A,abs(ans-temp*2));
    }


    cout << A << endl;


    return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> value(N);
  for (int i=0;i<N;i++){
    cin >> value.at(i);
  }
  vector<int> cost(N);
  for (int i=0;i<N;i++){
    cin >> cost.at(i);
  }
  int valuesum=0;
  int costsum=0;
  for (int i=0;i<N;i++){
    if(value.at(i)>cost.at(i)){
      valuesum+=value.at(i);
      costsum+=cost.at(i);
    }
  }
  
  cout << valuesum-costsum << endl;
}


Measured memory_bytes: 256
/* ***********************************************
Author        :yang12138
Created Time  :2017年04月13日 星期四 00时16分25秒
File Name     :D.cpp
************************************************ */
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int,int>pii;
#define lson (root<<1)
#define rson (root<<1|1)

const int N=1e5+10;
const int mod=1e9+7;

int a[N],b[N];

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",a+i);
	for(int i=1;i<=m;i++) scanf("%d",b+i);
	sort(a+1,a+n+1);
	sort(b+1,b+m+1);

	ll s1=0,s2=0;
	for(int i=1;i<m;i++){
		s1+=(ll)i*(m-i)*(b[i+1]-b[i]);
		s1%=mod;
	}

	for(int i=1;i<n;i++){
		s2+=(ll)i*(n-i)*(a[i+1]-a[i]);
		s2%=mod;
	}

	printf("%lld\n",s1*s2%mod);
    
    return 0;
}


Measured memory_bytes: 1024
p=[1]*100001
p[0]=p[1]=nil
(2...p.size).each{|i|
  next unless p[i]
  break unless i*i<p.size
  (i+i).step(p.size-1,i){|j|p[j]=nil}
}
s=[0]*100003
1.step(s.size-3,2).each{|i|s[i]+=s[i-2]+(p[i]&&p[((i+1)/2)] ? 1 : 0)}
puts gets.to_i.times.map{l,r=gets.split.map(&:to_i);s[r]-s[l-2]}


Measured memory_bytes: 4604
import * as fs from "fs";

const input = (fs.readFileSync("/dev/stdin", "utf8") as string).split("\n");
//const n = +input[0];
//const a = [];
//for(let i=0;i<n;i++){
//	a.push(input[i+1].split(" ").map((x:string):number=>+x));
//}

//const [n, m] = input[0].split(" ").map((x: string): number => +x);
//const a = input[1].split(" ").map((x: string): number => +x);

function compareFunc(a, b){
    return a-b;
}

const [n, d] = input[0].split(' ').map((x: string): number => +x);

const kanshi:number = d*2 +1;

if(n % kanshi === 0){
    console.log(n/kanshi);
}else{
    console.log(Math.floor(n/kanshi)+1);
}

Measured memory_bytes: 7500
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef long long LL;
#define sqr(x) ((x)*(x))
#define mp make_pair
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){
	int x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(int a){
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(int a){
    if(a<0){
    	a=-a; putchar('-');
	}
	write(a); puts("");
}
map<int,int> M;
map<int,int>::iterator it;
int n;
long long ans;
int main(){
	n=read();
	for(int i=1;i<=n;i++)M[read()]++;
	for(it=M.begin();it!=M.end();it++){
		int t1=it->first,t2=it->second;
		if(t2<t1)ans+=t2; else ans+=t2-t1;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 4736
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}
 
ll nCr(ll n, ll r){
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
 
//-----------------------ここから-----------
int main(void){
    int n;
    cin >> n;
    
    map<string, int> mp;
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        mp[s]++;
    }

    int ma = 0;
    for(auto &i : mp){
        ma = max(ma, i.second);
    }

    vector<string> ss;
    for(auto &i : mp){
        if(i.second == ma){
            ss.push_back(i.first);
        }
    }

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

    for(int i = 0; i < ss.size(); i++){
        cout << ss[i] << endl;
    }
}

Measured memory_bytes: 26868
#include<iostream>
#include<vector>

int main(){
	//入力機構
	size_t H,W;
	std::cin>>H>>W;
	std::vector<std::vector<char>> a(H,std::vector<char>(W,0));
	for(size_t i=0;i<H;i++){
		for(size_t j=0;j<W;j++){
			std::cin>>a[i][j];
		}
	}

	//処理機構
	//ある列が全て白であるなら、他の列・行を消してもその列は消せる。行についても同様。
	//また、ある列のいずれかの要素が白でない場合は、黒のマスを消す操作は不可能なので、その列は消せない。行についても同様。
	//つまり、列・行において、全ての要素が白であるものを探し、それを無視して行列を出力すればよい。
	std::vector<bool> rowFlag(W,false),columnFlag(H,false);//その行・列は無視せず出力するかどうか
	//rowFlag,columnFlagの計算
	for(size_t x=0;x<W;x++){
		for(size_t y=0;y<H;y++){
			if(a[y][x]=='#'){
				//1つでも黒があれば、その列は出力
				rowFlag[x]=true;
				break;
			}
		}
	}
	for(size_t y=0;y<H;y++){
		for(size_t x=0;x<W;x++){
			if(a[y][x]=='#'){
				//1つでも黒があれば、その行は出力
				columnFlag[y]=true;
				break;
			}
		}
	}

	//出力機構
	for(size_t y=0;y<H;y++){
		if(columnFlag[y]){
			for(size_t x=0;x<W;x++){
				if(rowFlag[x]){
					std::cout<<a[y][x];
				}
			}
			std::cout<<std::endl;
		}
	}

	return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <cmath>
#include <numeric>
#include <iomanip>

using namespace std;
long long a[15];
int main(void){
  int N;
  int K;
  cin >> N >> K;
  for(int i = 0; i < N; i++){
    cin >> a[i];
  }

  long long ans = LLONG_MAX;
  for(int bit_set = 0; bit_set < (1 << N); bit_set++){
    long long last_height = 0;
    long long tmp_ans = 0;
    int buliding_no = 0;
    for(int i = 0; i < N; i++){
      if(((bit_set >> i) & 1) == 1){
        buliding_no ++;
        if(last_height >= a[i]){
          tmp_ans += (last_height + 1) - a[i];
          last_height = (last_height + 1);
        } else {
          last_height = a[i];
        }
      }
      last_height = max(last_height, a[i]);
    }
    if(buliding_no >= K){
      ans = min(ans, tmp_ans);
      //cout << bit_set << " " << tmp_ans << endl;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
int acs(const void *a, const void *b){return *(int*)a - *(int*)b;} /* 1,2,3,4.. */
int des(const void *a, const void *b){return *(int*)b - *(int*)a;} /* 8,7,6,5.. */
int cmp_char(const void *a, const void *b){return *(char*)a - *(char*)b;} /* a,b,c,d.. */
int cmp_str(const void *a, const void *b){return strcmp(*(const char **)a, *(const char **)b);} /* aaa,aab.. */
#define min(a,b) (a < b ? a: b)
#define max(a,b) (a > b ? a: b)
#define rep(i, l, r) for (int i = l; i < r; i++)
#define MAX 100001
#define MOD 1000000007

typedef long long int lli;

int main(void) {
  char s[MAX];
  scanf("%s", s);

  int ans = 1000;
  rep(i, 0, strlen(s) - 2) {
    int num = (int)(s[i] - '0') * 100 + (int)(s[i + 1] - '0') * 10 + (int)(s[i + 2] - '0');
    ans = min(ans, abs(num - 753));
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
 
int main() {
  int h, w;
  string s[102];
  s[0] = "", s[h+1] = "";
  cin >> h >> w;
  for(int i=0; i<h; ++i) cin >> s[i+1];
  for(int j=0; j<w; ++j) {
    s[0] += "#";
    s[h+1] += "#";
  }
  for(int i=0; i<=h+1; ++i){
    s[i] = "#" + s[i] + "#";
   	cout << s[i] << endl;
  }
}

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

int main()
{
    int N, M;
    cin >> N;
    vector<string> s(N);
    for (int i = 0; i < N; i++)
        cin >> s.at(i);
    
    cin >> M;
    vector<string> t(M);
    for (int i = 0; i < M; i++)
    {
        cin >> t.at(i);
    }

    
    map<string, int> count;
    for (int i = 0; i < N; i++)
        count[s.at(i)] ++;
    
    for (int i = 0; i < M; i++)
        count[t.at(i)] --;

    int max = 0;
    for (auto x : count) {
        if (x.second > max) max = x.second;
    }
    cout << max << endl;
}


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

bool my_cmp(tuple<string, int , int> a, tuple<string, int , int> b)
{
	if ( get<0>(a) != get<0>(b) )
		return get<0>(a) < get<0>(b);
	if ( get<1>(a) != get<1>(b) )
		return get<1>(a) > get<1>(b);
	else
		return true;
}

int  main()
{
	int n;
	cin >> n;
	vector<tuple<string, int, int>> p;
	rep(i, n)
	{
		string s; int a;
		cin >> s >> a;
		p.emplace_back(s, a, i+1);
	}
	sort(p.begin(), p.end(), my_cmp);
	rep(i, n)
		cout << get<2>(p.at(i)) << endl;
	return (0);
}

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

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);

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

  int heightest = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] > a[heightest]) {
      heightest = i;
    }
  }
  vector<int> stack;
  for (int i = heightest; i >= 0; i--) {
    while (stack.size() && a[stack.back()] <= a[i]) stack.pop_back();
    stack.push_back(i);
  }

  map<int,long long> cnt;
  for (auto i : a) cnt[i]++;
  vector<long long> ans(n);

  for (int i = 1; i < (int) stack.size(); i++) {
    int high = a[stack[i - 1]];
    int low = a[stack[i]];
    auto it = cnt.upper_bound(low);
    while (it != cnt.end()) {
      ans[stack[i - 1]] += it->second * (it->first - low);
      cnt[low] += it->second;
      it++;
    }
    cnt.erase(cnt.upper_bound(low), cnt.end());
  }
  for (auto i : cnt) {
    ans[0] += i.second * i.first;
  }

  for (auto i : ans) {
    cout << i << '\n';
  }
  return 0;
}



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

//解説見た
using namespace std;

int main()
{
  int H,N;
  cin>>H>>N;
  if(H%N==0)
  {
    cout<<H/N<<endl;
  }
  else
  {
    cout<<H/N+1<<endl;
  }

  return 0;
}


Measured memory_bytes: 256
/*JOI 君は鉛筆を N 本買うために近くの文房具店に行くことにした． 
  文房具店では鉛筆が一定の本数ずつのセットで売られている．セット X は A 本で B 円，セット Y は C 本で D 円である． 
  JOI 君はセット X かセット Y の一方を選び，選んだセットをいくつか購入する．
  両方のセットを購入することはできない．N 本以上の鉛筆を得るために必要な金額の最小値を求めよ.*/
#include<iostream>
using namespace std;
int main(){
    int n,a,b,c,d;
    cin>>n>>a>>b>>c>>d;
    if((n+a-1)/a*b<=(n+c-1)/c*d){
      cout<<(n+a-1)/a*b<<endl;
    }
    else{
        cout<<(n+c-1)/c*d<<endl;
    }
}


Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
typedef long long   ll;
 
int gcd(int p, int q){
    if (p % q == 0){
        return q;
    }
    return gcd(q, p % q);
}
 
int main(){
    int K;
    cin >> K;
    int sum = 0;
    for (int i=0; i<K; i++){
        for (int j=0; j<K; j++){
            for (int k=0; k<K; k++){
                sum += gcd(gcd(i+1, j+1), k+1);
            }
        }
    }
    cout << sum << endl;
    
    return 0;
}

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

import sys
from collections import deque, Counter
import bisect
import math
from itertools import accumulate, product, permutations, combinations, groupby
from fractions import gcd 
import heapq
sys.setrecursionlimit(10**6)
#input = sys.stdin.readline #文字列入力のときは注意

n,k = [int(i) for i in input().split()]
print(n-k+1)



#if ok == 1:
#   print("Yes")
#else:
#   print("No")



Measured memory_bytes: 5888
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int cnt =0;

        for(int i =0;i<16;i++){
            for(int j =0;j<16;j++){
                if((i*4+j*7)==n){
                    cnt++;
                }
            }
        }

        if(cnt!=0){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 21844
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<climits>
typedef long long ll;
using namespace std;
int RD(){
    int out = 0,flag = 1;char c = getchar();
    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
    return flag * out;
    }
const int maxn = 1000019;
ll num,a[maxn];
int main(){
	num = RD();
	for(int i = 1;i <= 2 * num;i++)a[i] = RD();
	sort(a + 1,a + 1 + 2 * num);
	ll ans = 0;
	for(int i = 1;i <= 2 * num;i += 2)ans += a[i];
	printf("%lld\n",ans);
	return 0;
	}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX 334
#define MAX_L 17
#define INF 1e9
 
struct edge{
    int to,cost;
};
 
struct State{
    int cost,v,S;
    bool operator < (const State &s)const{
	return cost > s.cost;
    }
};
 
int N,M,L,S,T,restv[MAX_L],reste[MAX_L];
vector<edge> G[MAX_L];
int dist[1<<MAX_L][MAX_L];
 
string bit(int S){
    string res;
    for(int i = 0 ; i < L ; i++){
	if((S >> i) & 1) res += '1';
	else res += '0';
    }
    return res;
}
 
int dijkstra(){
    priority_queue<State> Q;
    Q.push((State){0,L,0});
    int ans = 0;
    for(int i = 0 ; i < (1<<L) ; i++){
	for(int j = 0 ; j <= L ; j++){
	    dist[i][j] = INF;
	}
    }
    dist[0][L] = 0;
    while(!Q.empty()){
	State s = Q.top(); Q.pop();
	int v = s.v;
	if(s.cost <= T && v == L){
	    ans = max(ans,__builtin_popcount(s.S));
	}
	if(s.cost >= T) continue;
	if(dist[s.S][v] < s.cost) continue;
	if(v != L){
	    if(!((s.S >> v) & 1)){
		int next = s.S | (1<<v);
		if(dist[s.S][v] + reste[v] < dist[next][v]){
		    dist[next][v] = dist[s.S][v] + reste[v];
		    Q.push((State){dist[next][v],v,next});
		}
	    }
	}
	for(int i = 0 ; i < (int)G[v].size() ; i++){
	    edge &e = G[v][i];
	    if(dist[s.S][v] + e.cost < dist[s.S][e.to]){
		dist[s.S][e.to] = dist[s.S][v] + e.cost;
		Q.push((State){dist[s.S][e.to],e.to,s.S});
	    }
	}
    }
    return ans;
}
 
int main(){
    while(cin >> N >> M >> L >> S >> T, N){
	int d[MAX][MAX];
	for(int i = 0 ; i < N ; i++){
	    for(int j = 0 ; j < N ; j++){
		if(i == j){
		    d[i][j] = 0;
		}else{
		    d[i][j] = INF;
		}
	    }
	}
	for(int i = 0 ; i < MAX_L ; i++){
	    G[i].clear();
	}
	S--;
	for(int i = 0 ; i < M ; i++){
	    int a,b,c;
	    cin >> a >> b >> c;
	    a--; b--;
	    d[a][b] = d[b][a] = c;
	}
	for(int k = 0 ; k < N ; k++){
	    for(int i = 0 ; i < N ; i++){
		for(int j = 0 ; j < N ; j++){
		    d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
		}
	    }
	}
	int restv[MAX_L];
	for(int i = 0 ; i < L ; i++){
	    cin >> restv[i] >> reste[i];
	    restv[i]--;
	}
	restv[L] = S; reste[L] = 0;
	for(int i = 0 ; i <= L ; i++){
	    for(int j = i+1 ; j <= L ; j++){
		int time = d[restv[i]][restv[j]];
		if(time == INF) continue;
		G[i].push_back((edge){j,time});
		G[j].push_back((edge){i,time});
	    }
	}
	cout << dijkstra() << endl;
    }
    return 0;
}

Measured memory_bytes: 28856
#include <stdio.h>
#include <math.h>

int main()
{
    long long int n,m,k;
    scanf("%lld %lld",&n,&m);
    long long int a[n][2],b[m][2];
    for(int i=0;i<n;i++)
        scanf("%lld %lld",&a[i][0],&a[i][1]);
    for(int i=0;i<m;i++)
        scanf("%lld %lld",&b[i][0],&b[i][1]);
    for(long long int i=0;i<n;i++)
    {long long int min=1000000000;
        for(long long int j=0;j<m;j++)
        {
            if(min>fabs(a[i][0]-b[j][0])+fabs(a[i][1]-b[j][1]))
            {
                k=j;
                min=fabs(a[i][0]-b[j][0])+fabs(a[i][1]-b[j][1]);
            }
        }
      printf("%lld",k+1);
        if(i!=n-1)
            printf("\n");
    }
}


Measured memory_bytes: 128
#include<iostream>
#include<cstdio>
#define ll long long
#define mod 1000000007
using namespace std;
int n,m;
ll ans=0,f[3010][3010][2];
int main(){
	scanf("%d%d",&n,&m);
	f[0][0][1]=1;
	for(register int i=1;i<=n;i++)f[0][i][0]=1;
	for(register int i=0;i<m;i++){
		for(register int j=0;j<=n;j++){
			for(register int k=0;k<2;k++){
				if(j){
					f[i+1][j-1][k|(j==1)]=(f[i+1][j-1][k|(j==1)]+f[i][j][k])%mod;
					f[i+1][j][k|(j==1)]=(f[i+1][j][k|(j==1)]+f[i][j][k])%mod;
				}
				if(j<n){
					f[i+1][j+1][k]=(f[i+1][j+1][k]+f[i][j][k])%mod;
					f[i+1][j][k]=(f[i+1][j][k]+f[i][j][k])%mod;
				}
			}

		}
	}
	for(register int i=0;i<=n;i++)ans=(ans+f[m][i][1])%mod;
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 141568
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>
#include <unordered_map>

#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define all(s) s.begin(), s.end()
#define fo(i, start, finish) for(int i = start; i <= finish; i ++)
#define y1 kdfjsalsdkf

const long long MXN = 2e5 + 10;
const long long MNN = 5e3 + 1;
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
const long long OO = 1e9 + 500;

typedef long long llong;
typedef unsigned long long ullong;

using namespace std;

llong n, k, b[MXN * 2], pos[MXN], d[64][MXN], contain[MXN];
vector<llong> v;

int main(){
    ios;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> b[i];
        b[i + n] = b[i];
    }
    for(int i = 2 * n - 1; i >= 0; i--){
        if (i < n) d[0][i] = pos[b[i]] - i + 1;
        pos[b[i]] = i;
    }
    for(int i = 1; i <= 60; i++){
        for(int j = 0; j < n; j++){
            d[i][j] = min(INF, d[i - 1][j] + d[i - 1][(j + d[i - 1][j]) % n]);
        }
    }
    llong cur = 0;
    for(int i = 60; i >= 0; i--){
        if (cur + d[i][cur % n] <= n * k) cur += d[i][cur % n];
    }
    for( ; cur < n * k; cur++){
        if(contain[b[cur % n]] == 0){
            v.pb(b[cur % n]);
            contain[b[cur % n]]++;
        } else {
            while(contain[b[cur % n]] != 0){
                contain[v[v.size() - 1]]--;
                v.pop_back();
            }
        }
    }
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << ' ';
    }
    return 0;
}


//
//
//


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

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;

#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) (x).begin(),(x).end()
constexpr auto INF = 4000000000; //4*10^9;
constexpr auto MOD = 1000000007; //10^9+7;

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

	int ans = 0;
	rep(i, s.size() / 2) {
		if (s[i] == s[s.size() - i - 1])continue;
		ans++;
	}

	cout << ans << endl;
}

Measured memory_bytes: 384
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define repi(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define repdi(i,a,b) for(ll i=(a)-1;i>=(b);--i)
#define repd(i,a) repdi(i,a,0)
#define itr(it,a) for( auto it = (a).begin(); it != (a).end(); ++it )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

using ll = long long;
using P = std::pair<ll, ll>;

constexpr ll INF = 1ll<<60;

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

template<class S, class T>
std::ostream& operator<< ( std::ostream& out, const std::pair<S,T>& a )
{ std::cout << '(' << a.first << ", " << a.second << ')'; return out; }

template<class T>
std::ostream &operator<< ( std::ostream& out, const std::vector<T>& a )
{ std::cout << '['; rep( i, a.size() ){ std::cout << a[i]; if( i != a.size()-1 ) std::cout << ", "; } std::cout << ']'; return out; }

ll D;

int main()
{
  std::cin >> D;

  std::string ans = "Christmas";

  rep( i, 25-D )
    ans += " Eve";

  std::cout << ans << std::endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); i++)
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
using namespace std;
typedef long long ll;

int main(){
    string a, b;
    cin >> a >> b;
    if(a == b) cout << "H" << endl;
    else cout << "D" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    int l = 100001;
    ll v[l]{};
    ll A[N];
    ll s = 0;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        v[A[i]]++;
        s += A[i];
    }
    int Q;
    cin >> Q;
    ll B[Q], C[Q];
    for (int i = 0; i < Q; i++) {
        cin >> B[i] >> C[i];
    }
    for (int i = 0; i < Q; i++) {
        ll e = C[i] * v[B[i]] - B[i] * v[B[i]];
        s += e;
        v[C[i]] += v[B[i]];
        v[B[i]] = 0;
        cout << s << "\n";
    }
    return 0;
}

Measured memory_bytes: 6720
/*
 Remember not to use arithmetic operation in double while comparision 

 priority of uses
 array > maps > unordered_maps
*/

#include<bits/stdc++.h>
#define lli long long int
#define vl vector<lli>
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define pll pair<lli,lli>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	int n,k;
	cin>>n>>k;
	vl A(n),DP(n,INT_MAX);
	for(auto &x:A)
		cin>>x;
	DP[0]=0;
	for(int i=1;i<n;i++)
	{
		for(int j=max(0,i-k);j<i;j++)
			DP[i]=min(DP[i],DP[j]+abs(A[j]-A[i]));
	}
	cout<<DP[n-1];
	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <string>
#include <set>

#include <regex>
#include <locale>
#include <iomanip>

using namespace std;
using ll = long long;

#define OVERLOAD3(_1,_2,_3,name,...) name
#define REP(i,n) REPI(i,0,n)
#define REPI(i,a,b) for(int i=int(a),i##_Len=int(b);i<i##_Len;++i)
#define rep(...) OVERLOAD3(__VA_ARGS__,REPI,REP,)(__VA_ARGS__)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

int main () {
  int a, b; cin >> a >> b;
  cout << ((a*b)%2 ? "Odd" : "Even") << endl;
}

Measured memory_bytes: 3044
from collections import deque
n,m = map(int,input().split())
edge = [[]for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
#print(edge)
ans = [0]*(n+1)
#print(ans)

def bfs(x):
    q = deque([])
    q.append(x)
    ans[1]=1
    while len(q)>0:
        pos = q.popleft()
        
        for i in edge[pos]:
            if ans[i] == 0:
                q.append(i)
                ans[i] = pos
    return ans

ans = bfs(1)
#print(ans)
ans.pop(0)
if 0 in ans:
  print("No")
else:
  print("Yes")
  for i in range(1,len(ans)):
    print(ans[i])

Measured memory_bytes: 34136
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
int H,W,N;
string o,s[1000];
bool vis[1000][1000];
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
bool is(int x,int y){
	return 0<=x&&x<H&&0<=y&&y<W&&s[x][y]!='#';
}
typedef pair<int,int> P;
vector<P> vc[1000001];
int main(){
	while(true){
		cin>>H>>W>>N;
		if(H==0) break;
		rep(i,N+1) vc[i].clear();
		rep(i,H) rep(j,W) vis[i][j]=0;
		cin>>o;
		rep(i,H) cin>>s[i];
		rep(i,H) rep(j,W) if(s[i][j]=='S'){
			int x=i,y=j;
			while(is(x,y)){
				vc[0].pb(P(x,y)),vis[x][y]=1;
				x--;
			}
		}
		int e[4]={0,-1,-1,-1};
		int D=0;
		rep1(i,N){
			D=(D+(o[i-1]=='L'?1:3))%4;
			for(int j=e[D]+1;j<i;j++){
				for(P p:vc[j]){
					int x=p.fs+dx[D],y=p.sc+dy[D];
					while(is(x,y)&&!vis[x][y]){
						vis[x][y]=1;
						vc[i].pb(P(x,y));
						x+=dx[D],y+=dy[D];
					}
				}
			}
			e[D]=i;
		}
		rep(i,H) rep(j,W) if(s[i][j]=='G'){
			if(vis[i][j]) puts("Yes");
			else puts("No");
		}
	}
}

Measured memory_bytes: 35752