akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define whlie while
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define rep(i,N) for(int i = 0; i < (N); i++)
#define repr(i,N) for(auto i = (N) - 1; i >= 0; i -= 1)
#define each(x,v) for(auto& x : v)
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define vrep(v,it) for(auto it = v.begin(); it != v.end(); it++)
#define vrepr(v,it) for(auto it = v.rbegin(); it != v.rend(); it++)
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
#define rand mtrand
#ifdef NyaanDebug
  #include "NyaanDebug.h"
  #define trc(...) do { cout << #__VA_ARGS__ << " = "; dbg_out(__VA_ARGS__);} while(0)
  #define trca(v,...) do { cout << #v << " = "; array_out(v , ##__VA_ARGS__);cout << endl;} while(0)
#else
  #define trc(...)
  #define trca(...)
#endif
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector< vector<int> >;
constexpr int inf = 1001001001;
constexpr ll infLL = 0x1FFFFFFFFFFFFFFFLL;
struct IoSetupNya {IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(15);} } iosetupnya;
template<typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template<typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; }
template<typename T, typename U> ostream& operator <<(ostream& os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; }
template<typename T, typename U> istream& operator >>(istream& is, pair<T, U> &p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator <<(ostream& os, const vector<T> &v) { int s = (int)v.size(); rep(i,s) os << (i ? " " : "") << v[i]; return os; }
template<typename T> istream& operator >>(istream& is, vector<T> &v) { for(auto &x : v) is >> x; return is; }
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
template<typename T>void die(T x){out(x); exit(0);}

random_device seed_gen; mt19937_64 mtrand(seed_gen());
constexpr int MOD = 1000000007;
//////////////////////////////////////////

int main(){
  ini(N);
  vi a(N); in(a);

  int l = 0, r = 0;
  int ans = 0;
  while(r != N){
    while(r != N && a[r] == a[l]) r++;
    ans += (r - l) / 2;
    l = r;
  }
  out(ans);
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <vector>

int bubbleSort(std::vector<int> &A, int N); 

int main(void) {
    int N;
    std::cin >> N;
    std::vector<int> A(N, 0);
    for (int i = 0; i < N; i++) {
        std::cin >> A[i];
    }
    int trade = bubbleSort(A, N);
    for (int i = 0; i < N; i++) {
        std::cout << A[i];
        if (i < N - 1) {
            std::cout << " ";
        }
    }
    std::cout << std::endl;
    std::cout << trade << std::endl;
    return EXIT_SUCCESS;
}

int bubbleSort(std::vector<int> &A, int N) {
    int trade = 0;
    bool flag = 1;
    int temp;
    while (flag) {
        flag = 0;
        for (int j = N - 1; j >= 1; j--) {
            if (A[j] < A[j - 1]) {
                temp = A[j];
                A[j] = A[j - 1];
                A[j - 1] = temp;
                flag = 1;
                trade++;
            }
        }
    }
    return trade;
}

Measured memory_bytes: 3104
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 100000
using namespace std;

int len,ans=0;
char c[N+5];

int main(void){
	scanf("%d",&len);
	scanf("%s",c+1);
	for(int i=2;i<=len;i++){
		if(c[i]==c[i-1])continue;
		ans++;
	}
	ans++;
	printf("%d",ans); 
}

Measured memory_bytes: 256
<?php
$N = fgets(STDIN);
$A = explode(' ', fgets(STDIN));

$result = [];
foreach ($A as $A_i) {
    $result[$A_i - 1] += 1;
}

$i = 0;
while ($i < $N) {
    $result_i = $result[$i] ? $result[$i] : 0;
    echo "{$result_i}\n";
    $i++;
}

Measured memory_bytes: 39732
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	b += MOD;
	a += b;
	a %= MOD;
}

int main(void){
	int n,i,j,c;
	ll k,a[100100],x=0ll,ans=0ll;
	cin >> n >> k;
	for(i=0; i<n; ++i){
		cin >> a[i];
	}
	for(j=40; j>=0; --j){
		if(((1ll<<j)+x)>k){
			for(i=0; i<n; ++i){
				if((1ll<<j)&a[i]){
					ans += (1ll<<j);
				}
			}
			continue;
		}
		c = 0ll;
		for(i=0; i<n; ++i){
			if((1ll<<j)&a[i]){
				++c;
			}
		}
		if(c*2<n){
			ans += (1ll<<j)*(n-c);
			x += (1ll<<j);
		}else{
			ans += (1ll<<j)*c;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1024
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
#define MK make_pair
const ll E=1e17+7;
const ll MOD=1000000007;




int main(){
    ll n,a,b;
    cin>>n>>a>>b;
    vector<ll> dis;
    for(int i=0;i<n;i++){
        ll b;
        cin>>b;
        dis.push_back(b);
    }
    ll ans=0;
    for(int i=1;i<n;i++){
        ans+=min((dis[i]-dis[i-1])*a,b);
    }
    cout<<ans<<endl;
    
    return 0;
}

Measured memory_bytes: 1400
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define dup(x,y) (((x)+(y)-1)/(y))
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pii;
const double EPS = 1e-10;
const int INF = 1e9;
const ll LINF = 1e15;
const int MOD = 1000000007;
const double PI = acos(-1);
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

int main() {
	ll a, b, c, d;
	cin >> a >> b >> c >> d;
	ll ans = max(a*c, a*d);
	ans = max(ans,max(b*c,b*d));
	cout << ans << endl;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
 
int gcd(int a, int b)
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}
int main(){
  int k;
  cin >> k;
  int ans=0;
  for(int i=1;i<=k;i++){
    for(int j=1;j<=k;j++){
      for(int l=1;l<=k;l++){
        int num=gcd(gcd(i,j),l);
        ans+=num;
      }
    }
  }
  cout << ans << endl;
}


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

int main() {

  while(1) {

    int H, W;
    cin >> H >> W;

    if (H == 0 && W == 0) {
      return 0;
    }

    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        cout << "#";
      }
      cout << endl;
    }
    cout << endl;

  }

  return 0;

}


Measured memory_bytes: 3092
import java.awt.Point;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;


public class Main {
	
	static int[][] smap;
	static int[][] nummap;
	static int w;
	static int h;
	static Queue<Point> queue = new LinkedList<Point>();
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		while(true){
			
			w = sc.nextInt();
			h = sc.nextInt();
			
			if(w == 0 && h == 0){
				break;
			}
			
			int[][] map = new int[(w * 2) - 1][(h * 2) - 1];
			
			for(int i = 0; i < (h * 2) - 1; i++){
				for(int j = 1; j < (w * 2) - 1; j++){
					map[j][i] = sc.nextInt();
					j++;
				}
				if(i < (h * 2) - 2){
					i++;
					for(int j = 0; j < (w * 2) - 1; j++){
						map[j][i] = sc.nextInt();
						j++;
					}
				}
			}
			
			for(int i = 0; i < (h * 2) - 1; i++){
				for(int j = 0; j < (w * 2) - 1; j++){
					map[j][i] = 0;
					j++;
				}
				if(i < (h * 2) - 2){
					i++;
					for(int j = 1; j < (w * 2) - 1; j++){
						map[j][i] = 0;
						j++;
					}
				}
			}
			
			smap = map;
			nummap = new int[(w * 2) - 1][(h * 2) - 1];
			
			for(int i = 0; i < (h * 2) - 1; i++){
				for(int j = 0; j < (w * 2) - 1; j++){
					nummap[j][i] = Integer.MAX_VALUE;
				}
			}

			queue.clear();
			
			amazing(0,0,0);
			int num = 1;
			int size = 0;
			
			while(true){
				size = queue.size();
				
				for(int i = 0; i < size; i++){
					amazing(queue.peek().x,queue.poll().y , num);
				}
				if(queue.isEmpty() || nummap[(w * 2) - 2][(h * 2) - 2] != Integer.MAX_VALUE){
					break;
				}
				num++;
			}
			if(nummap[(w * 2) - 2][(h * 2) - 2] == Integer.MAX_VALUE){
				System.out.println(0);
			}else{
				System.out.println(nummap[(w * 2) - 2][(h * 2) - 2] + 1);
			}
		}
		
	}

	private static void amazing(int x, int y, int num) {
		nummap[x][y] = num;
		
		if((x + 2) <= (w * 2 - 2) && smap[x + 1][y] == 0 && nummap[x + 2][y] > num + 1){
			queue.offer(new Point(x + 2, y));
			nummap[x + 2][y] = num + 1;
		}
		if((x - 2) >= 0 && smap[x - 1][y] == 0 && nummap[x - 2][y] > num + 1){
			queue.offer(new Point(x - 2, y));
			nummap[x - 2][y] = num + 1;
		}
		if((y + 2) <= (h * 2) - 2 && smap[x][y + 1] == 0 && nummap[x][y + 2] > num + 1){
			queue.offer(new Point(x, y + 2));
			nummap[x][y + 2] = num + 1;
		}
		if((y - 2) >= 0 && smap[x][y - 1] == 0 && nummap[x][y - 2] > num + 1){
			queue.offer(new Point(x, y - 2));
			nummap[x][y - 2] = num + 1;
		}
		
	}

}

Measured memory_bytes: 13000
using System;
using static System.Console;
using static System.Math;
using System.Numerics;
using System.Collections.Generic;
using System.Linq;


public class Program
{
    public static void Main(string[] args)
    {
        var s = myRead.readIntArray();
        int t = s[2] / s[1];
      	t += s[2] % s[1] != 0 ? 1 : 0;
      	int o = s[0] / s[3];
      	o += s[0] % s[3] != 0 ? 1 : 0;
      	var ans = t <= o ? "Yes" : "No";
      	WriteLine(ans);
    }
}
public static class myRead
{
    public static int readInt() { return int.Parse(ReadLine()); }
    public static long readLong() { return long.Parse(ReadLine()); }
    public static string reatStr() { return ReadLine(); }
    public static int[] readIntArray() { return ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] readLongArray() { return ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] readStrArray() { return ReadLine().Split(' '); }
}


public static class MyMath
{
    public static long Factorical(long n)
    { return n <= 1 ? 1L : n * Factorical(n - 1); }
    public static long Permutation(long n, long m)
    { return m == 0 ? 1L : (m == n) ? Permutation(n, m - 1) : n * Permutation(n - 1, m - 1); }
    public static long Combination(long n, long m)
    { return n - m > m ? Permutation(n, m) / Factorical(m) : Permutation(n, n - m) / Factorical(n - m); }
    public static long Gcd(long n, long m)
    { return n % m == 0 ? m : Gcd(m, n % m); }
    public static long Lcm(long n, long m)
    { return n * m / Gcd(n, m); }
    public static long Pow(long n, long m)
    { return m == 0 ? 1L : m == 1 ? n : n * Pow(n, m - 1); }
}




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

vector<long long > vi;

int main(){
    int n;
    scanf("%d",&n);
    int k;
    scanf("%d",&k);
    for(int i=0;i<n;i++){
        long long s;
        scanf("%lld",&s);
        vi.push_back(s);
    }
    long long sum=0;
    sort(vi.begin(),vi.end());
    for(int i=0;i<k;i++){
        sum+=vi[i];
    }
    printf("%lld",sum);
    return 0;
}


Measured memory_bytes: 3840
#include<iostream>

using namespace std;

int a[2][1000], dp[2][1000];

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

	dp[0][0] = a[0][0];
	dp[1][0] = a[0][0] + a[1][0];

	for(int j=1;j<n;j++)
		dp[0][j] = a[0][j] + dp[0][j-1];

	for(int j=1;j<n;j++){
		dp[1][j] = max(dp[1][j-1], dp[0][j]) + a[1][j];
	}

	cout<<dp[1][n-1]<<endl;
}



Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <map>
#include <tuple>
#include <vector>

using namespace std;

int main() {
    int N;

    cin >> N;

    vector< int > t(N + 1), x(N + 1), y(N + 1);

    t[0] = x[0] = y[0] = 0;
    for (int i = 1; i <= N; i++) {
        cin >> t[i] >> x[i] >> y[i];
    }

    // t_i < t_i+1
    int move_num = 0;
    int distance = 0;
    for (int i = 1; i <= N; i++) {
        move_num = t[i] - t[i - 1];
        distance = abs(x[i] - x[i - 1]) + abs(y[i] - y[i - 1]);

        if (distance > move_num) {
            cout << "No" << endl;
            return 0;
        } else {
            if ((move_num - distance) % 2 != 0) {
                cout << "No" << endl;
                return 0;
            }
        }
    }

    cout << "Yes" << endl;
}

Measured memory_bytes: 1408
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<string>
long long  INF=1'0000'0000'0000'0000'00;
using namespace std;

int main(){

int x,y,z;
long long k;
cin>>x>>y>>z>>k;

vector<long long>A(x);
vector<long long>B(y);
vector<long long>C(z);
long long t;
for(int i=0;i<x;i++){
cin>>A[i];
}
for(int i=0;i<y;i++){
cin>>B[i];
}
for(int i=0;i<z;i++){
cin>>t;
C[i]=-t;
}
vector<long long >ans(x*y);
t=0;
for(int i=0;i<x;i++){
    for(int l=0;l<y;l++){
        ans[t]=-(A[i]+B[l]);
        t++;
    }
}
sort(ans.begin(),ans.end());


t=0;
vector<long long >Ans(k*z);
for(int i=0;i<min(k,(long long) x*y);i++){
    for(int l=0;l<z;l++){
        Ans[t++]=ans[i]+C[l];
    }
}
sort(Ans.begin(),Ans.end());

for(int i=0;i<k;i++){
    cout<<-Ans[i]<<endl;
}
    

 return 0;
}

Measured memory_bytes: 31616
#include <iostream>
#include<time.h>
#include<string>
#include<cstring>
#include <cstdio>
#include<utility>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<bitset>
#include<queue>
#include<stack>
#include<set>
#include <limits>
#include <climits>
#include <numeric>
#include<cassert>
#include<cctype>
#include<iterator>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long LL;
typedef vector<ll>VI;
typedef vector<bool>VB;
typedef pair<ll,ll>P;
typedef pair<double,double>P_D;
#define VV(T) vector<vector<T>>
#define PI 3.1415926535897932384626433832795
#define rep(i, n) for (ll i = 0; i < (ll)n; i++)
#define reprev(i, n) for (ll i = (ll)n - 1; i >= 0; i--)
#define bitrep(bit,A) for(int bit=A; ;bit=(bit-1)&A)
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) (ll)((a).size())
#define c_max(a, b) (((ll)a)>((ll)b)?(a):(b))
#define c_min(a,b) (((ll)a)<((ll)b)?(a):(b))
#define chmax(x,a) x=c_max(x,a)
#define chmin(x,a) x=c_min(x,a)
#define vmax(v) *max_element(ALL(v))
#define vmin(v) *min_element(ALL(v))
#define SORT(c) stable_sort(ALL(c))
#define $(x) {cout<<#x<<" = " <<(x)<<endl;}
#define fi first
#define se second
#define MAX 100100//5
#define MAX2 200100
#define MAX_6 1001001//6
#define MAX_7 10010010//7
#define SENTINEL 2000000000//9
#define NIL -1
#define MOD 1000000007
#define INF 1<<30
#define INFTY 1000000000000000001LL
#define MAX_INT INT_MAX
#define Endl '\n'
#define greater greater<int>()
inline ll GCD(ll a,ll b){return b?GCD(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/GCD(a,b);}
// g++ -o a a.cpp -Wall -lm -std=c++14

int main(){
    ll A;double B;
    cin>>A>>B;
    int Bz=round(B*100);
    ll ans=A*Bz/100;
    cout<<ans<<endl;
}

Measured memory_bytes: 3744
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int count = sc.nextInt();
		int[][] house = new int[4][30];

		for(int i = 0;i < house.length; i ++) {
			for(int j = 0;j < house[i].length; j++){
				house[i][j] = 0;
			}

		}

		for(int i = 0;i < count;i++) {
			int houseNum = sc.nextInt();
			int roomNum = (Integer.parseInt(sc.next()) - 1) * 10 + (Integer.parseInt(sc.next()) - 1);
			int member = sc.nextInt();
			house[houseNum - 1][roomNum] += member;

		}

		for(int i = 0;i < house.length;i++) {
			for(int j = 0;j < house[i].length;j++) {
				if(j != 0 && j % 10 == 0) {
					System.out.println();
				}
				System.out.print(" " +  house[i][j]);

			}
			System.out.println();
			if(i != 3) {
				for(int j = 0;j < 20 ;j++) {
					System.out.print("#");
				}
				System.out.println();
			}
		}

	}
}

Measured memory_bytes: 28960
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
	ll a=0,b=getchar(),c=1;
	while(!isdigit(b))c=b=='-'?-1:1,b=getchar();
	while(isdigit(b))a=a*10+b-'0',b=getchar();
	return a*c;
}
set<ll> m;
ll a,b,c,d,ans,n,s[100005];
int main(){
	n=read();
    m.insert(0),m.insert(n+1);
    for(ll i=1;i<=n;i++)
    	a=read(),s[a-1]=i;
    for(ll i=n-1;i>=0;i--){
        m.insert(s[i]);
        auto x=m.find(s[i]),y=x;
        x++,c=*x;
        if(c==n+1)d=n+1;
        else x++,d=*x;
        y--,b=*y;
        if(b==0)a=0;
        else y--,a=*y;
        ans+=((d-c)*(s[i]-b)+(b-a)*(c-s[i]))*(i+1);
    }
    printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 5760
#import sys
#input = sys.stdin.buffer.readline
from collections import deque

def main():
    H,W = map(int,input().split())
    S = [list(str(input())) for _ in range(H)]
    INF = float('inf')
    
    def maiz(x,y):
        if S[x][y] == "#":
            return -1
        else:
            length = [[INF for _ in range(W)] for _ in range(H)]
            length[x][y] = 0
            dx,dy = [1,0,-1,0],[0,1,0,-1]
            queue = deque()
            queue.append((x,y))
            while queue:
                x,y = queue.popleft()
                for i in range(4):
                    nx,ny = x+dx[i],y+dy[i]
                    if (0 <= nx and nx < H and 0 <= ny and ny < W and S[nx][ny] == "." and length[nx][ny] == INF):
                        queue.append((nx,ny))
                        length[nx][ny] = min(length[nx][ny],length[x][y] + 1)
            num = 0
            for i in range(H):
                for j in range(W):
                    if length[i][j] != INF:
                        num = max(num,length[i][j])
            return num
    
    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(ans,maiz(i,j))
            
    print(ans)
        
if __name__ == "__main__":
    main()

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
const int MAXN=20;
const int MAXM=2<<16+1;
const int mo=1e9+7;
int n,m,a[MAXN],bit[MAXN],c[MAXM];
int fac[MAXM],inv[MAXM],dp[MAXN][MAXM];
int power(int x,int k)
{
	int cnt=1;
	while(k){
		if(k&1) cnt=cnt*x%mo;
		x=x*x%mo;
		k>>=1;
	}
	return cnt;
}
int C(int x,int y){return 1ll*fac[x]*inv[y]%mo*inv[x-y]%mo;}
main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>a[i];
	reverse(a+1,a+m+1);
	for(int i=0;i<=n-1;i++) bit[i]=1<<i;
	int cnt=1<<n;fac[0]=1;
	for(int i=1;i<=cnt;i++)
		fac[i]=1ll*fac[i-1]*i%mo;
	inv[cnt]=power(fac[cnt],mo-2);
	for(int i=cnt-1;i>=0;i--)
		inv[i]=inv[i+1]*(i+1ll)%mo;
	int u=(1<<n)-1;dp[0][0]=1;
	for(int i=1;i<=m;i++)
		for(int s=0;s<=u;s++){
			int l=cnt-a[i]+1-s;
			dp[i][s]=(dp[i][s]+dp[i-1][s])%mo;
			for(int j=0;j<=n-1;j++){
				if(l<bit[j]) break;
				if(bit[j]&s) continue;
				dp[i][s^bit[j]]=(dp[i][s^bit[j]]+(1ll*dp[i-1][s]*C(l-1,bit[j]-1))%mo*fac[bit[j]]%mo)%mo;
			}
		}
	int ans=fac[cnt-1]; c[0]=1;
	for(int s=1;s<=u;s++){
		c[s]=-c[s-(s&-s)];
		ans=(ans+1ll*c[s]*dp[m][s]*fac[cnt-1-s]%mo)%mo;
	}
	ans=(1ll*ans*cnt%mo+mo)%mo;
	cout<<ans;
}

Measured memory_bytes: 39168
n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)]
dp = [0] * 3
for a, b, c in abc:
    dp = [max(dp[1:]) + a, max(dp[0], dp[2]) + b, max(dp[:2]) + c]
print(max(dp))


Measured memory_bytes: 30576
s = input()
q = int(input())
qs = [input().split() for i in range(q)]
n = False
left= right = ""
for operation in qs:
    if operation[0] == '1':
        n = not n
    if operation[0] == '2':
        t , f, c = operation
        f = int(f)
        if n:
            f = 1 if f != 1 else 2
        if f == 1:
            left=c+left
        elif f == 2:
            right+=c
s = left+s+right
print(s[::-1] if n else s)

Measured memory_bytes: 41460
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main(void){
  int N, T;
  cin >> N >> T;
  vector<int> c, t;
  c.resize(N);

  t.resize(N);
  for (int i = 0; i < N;i++){
    cin >> c[i] >> t[i];
  }

  int min=-1;

  for (int i = 0; i < N;i++){
    if (t[i] > T){
      continue;
    }
    if(min==-1 || min>c[i]){
      min = c[i];
    }
  }

  if(min==-1){
    cout << "TLE" << endl;
  }else{
    cout << min << endl;
  }
}


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

int main(){
  int A,B,C,K;
  cin >> A >> B >> C;
  cin >> K;
  int l=0,m;
  if(A < B) m = B;
  else if(A < 2*B){m = 2*B; l++;}
  else if(A < 4*B){m = 4*B; l += 2;}
  else{ m = 8*B; l += 3;}
  A = m;
  B = C;
  if(A < B) m = B;
  else if(A < 2*B){m = 2*B; l++;}
  else if(A < 4*B){m = 4*B; l += 2;}
  else if(A < 8*B){ m = 8*B; l += 3;}
  else l += 4;
  
  if(K < l) cout << "No";
  else cout << "Yes";
 
  return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,a,b;
  cin >> n;
  vector<vector<int>> adj(n+1);
  vector<int> c(n),cnt(n+1),val(n+1);
  for(int i = 1; i < n; ++i){
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
    ++cnt[a];
    ++cnt[b];
  }
  for(int i = 0; i < n; ++i) cin >> c[i];
  sort(begin(c),end(c));
  int idx = 0;
  vector<bool> vu(n+1);
  while(true){
    bool ok = true;
    for(int i = 1; i <= n; ++i){
      if(!vu[i] and cnt[i] <= 1){
        vu[i] = true;
        val[i] = c[idx];
        ++idx;
        for(int j : adj[i]) --cnt[j];
        ok = false;
        break;
      }
    }
    if(ok) break;
  }
  int tot = 0;
  for(int i = 1; i < n; ++i){
    for(int j : adj[i]){
      if(j > i) tot += min(val[i],val[j]);
    }
  }
  cout << tot << endl;
  for(int i = 1; i <= n; ++i) cout << val[i] << ' ';
  return 0;
}

Measured memory_bytes: 1024
import itertools

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

for i in range(h):
    for j in range(w):
        cnt = 0
        if s[i][j] != "#":
            for dx, dy in itertools.product([-1, 0, 1], repeat=2):
                y = i+dy
                x = j+dx
                if y < 0 or y >= h:
                    continue
                if x < 0 or x >= w:
                    continue
                if s[y][x] == "#":
                    cnt += 1
            s[i][j] = str(cnt)

for i in range(h):
    print(''.join(s[i]))


Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;


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

    if (k > (n-1)*(n-2)/2){
        cout << -1 << endl;
        return 0;
    }

    vector<P> ans;

    rep(i, n-1) ans.push_back(make_pair(1, i+2));

    int cnt = (n-1)*(n-2)/2 - k;

    if (cnt == 0) {
        cout << ans.size() << endl;
        rep(j, ans.size()) cout << ans[j].first << " " << ans[j].second << endl;
        return 0;
    }

    for(int p = 2; p <= n; p++){
        for(int q = p+1; q <= n; q++){
            ans.push_back(make_pair(p,q));
            cnt--;
            if (cnt == 0) {
                cout << ans.size() << endl;
                rep(j, ans.size()) cout << ans[j].first << " " << ans[j].second << endl;
                return 0;
            }
        }
    }
}


Measured memory_bytes: 512
#include "bits/stdc++.h"

using Weight = int;
using Flow = int;
struct Edge {
	int src, dst;
	Weight weight;
	Flow cap;
	Edge() : src(0), dst(0), weight(0) {}
	Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) {}
};
using Edges = std::vector<Edge>;
using Graph = std::vector<Edges>;
using Array = std::vector<Weight>;
using Matrix = std::vector<Array>;

void add_edge(Graph &g, int a, int b, Weight w = 1) {
	g[a].emplace_back(a, b, w);
	g[b].emplace_back(b, a, w);
}
void add_arc(Graph &g, int a, int b, Weight w = 1) { g[a].emplace_back(a, b, w); }

bool operator<(const Edge &e, const Edge &f) { return e.weight > f.weight; }
std::pair<Weight, Edges> prim(const Graph &g, int r = 0) {
	Edges T;
	Weight total = 0;
	std::vector<int> vis(g.size());
	std::priority_queue<Edge> q;
	q.emplace(-1, r, 0);
	while (q.size()) {
		Edge e = q.top();
		q.pop();
		if (vis[e.dst]) continue;
		vis[e.dst] = true;
		total += e.weight;
		if (e.src != -1) T.emplace_back(e);
		for (auto &f : g[e.dst])
			if (!vis[f.dst]) q.emplace(f);
	}
	return std::make_pair(total, T);
}
int main() {
	int N;
	std::cin >> N;
	Graph g(N+1);
	std::vector<std::pair<int, int>> dist_x, dist_y;
	
	for (int i = 1; i <= N; i++) {
		int x, y;
		std::cin >> x >> y;
		dist_x.emplace_back(std::make_pair(x, i));
		dist_y.emplace_back(std::make_pair(y, i));
	}
	std::sort(begin(dist_x), end(dist_x));
	std::sort(begin(dist_y), end(dist_y));

	// add
	for (int i = 1; i < dist_x.size(); i++) {
		auto& p = dist_x[i - 1];
		auto& q = dist_x[i];
		add_edge(g, p.second, q.second, q.first - p.first);
	}
	
	for (int i = 1; i < dist_y.size(); i++) {
		auto& p = dist_y[i - 1];
		auto& q = dist_y[i];
		add_edge(g, p.second, q.second, q.first - p.first);
	}

	std::cout << prim(g, 1).first << std::endl;

	return 0;
}

Measured memory_bytes: 18408
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define f first
#define s second
using namespace std;
template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ";
    return os << "}";
}
typedef long long ll;
const int INF = 1e9;
const ll INFl = 1e18;
typedef pair<int,int> pii;
typedef vector<int> vi;

void solve() {
	int a, b, c, d, k; cin >> a >> b >> c >> d >> k;
	int Time = (c - a) * 60 + d - b;
	cout << Time - k << '\n';
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1;
	//cin >> q;
	while (q--) {
		solve();
	}
	return 0;
}


Measured memory_bytes: 3636
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import sys
sys.setrecursionlimit(10**5)

def main():
  n, m = map(int, input().split())
  luf = [-1] * (n+1)
  
  def find(x):
    if luf[x] < 0:
      return x
    else:
      luf[x] = find(luf[x])
      return luf[x]
  
  def union(x, y):
    px, py = find(x), find(y)
    if px == py:
      return
    if px < py:
      px, py = py, px
    luf[px] += luf[py]
    luf[py] = px
  
  for _ in range(m):
    x, y, z = map(int, input().split())
    union(x, y)
#   print(luf)
  print(sum([x<0 for x in luf[1:]]))

if __name__=='__main__':
  main()



Measured memory_bytes: 7288
//Ruthless Coding 
#include <bits/stdc++.h>

#define uni(x)      (x).resize(unique(ALL(x)) - (x).begin())
#define fprint(v)   for(auto x : v) cout << x << ' '
#define ALL(x)      (x).begin(), (x).end()
#define PI          3.14159265358979323846
#define MP(x, y)    make_pair(x, y)
#define SZ(x)       int((x).size())
#define PB(x)       push_back(x)
#define ld          long double
#define ll          long long
#define S           second 
#define F           first
#define nl          '\n'

using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
mt19937_64 rnd;

const int N = 2e5 + 5;
ll bit[N];
void upd(int idx, ll val){
    for(; idx < N; idx += idx & -idx){
        bit[idx] += val;
    }
}
ll sum(ll idx){
    ll res = 0;
    for(; idx > 0; idx -= idx & -idx){
        res += bit[idx];
    }
    return res;
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    ll n, k;
    cin >> n >> k;
    map<ll, ll> mp;
    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        upd(a, b);
    }
    ll lo = 0, hi = 1e5 + 1;
    while(hi - lo > 1){
        ll mid = lo + hi >> 1;
        ll yo = sum(mid);
        ll yo1 = sum(mid - 1);
        if(yo1 < k && k <= yo){
            cout << mid;
            break;
        }else if(k > yo) lo = mid;
        else hi = mid;
    }
    return 0;
}
/*
    *** Most Impo.. -> check base case always
    1. Overflow Check (*, +)
    2. Index check (0 - based or 1 - based)
    3. Check for n = 1, 2, 3, 4....
    4. Corner Cases
*/

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

using namespace std;

int main(void) {
    int N;cin>>N;
    vector<int> A(N);
    for(int i = 0;i < N; i++){
        cin>>A[i];
    }
    int cnt = 0;
    for(int i = 0; i < A.size(); i++){
        if(A[i] != i+1)cnt++;
    }

    if(cnt <= 2)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define LD long double

using namespace std;

int mod = 1e9 + 7;

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

    ll n;
    cin >> n;

    ll sum = 0;
    for(ll i = 1; i * i <= n; i++) {
    	if(n % i != 0LL) {
    		continue;
    	}
    	ll q = n / i;
    	if(q != 1) {
    		ll x = q - 1;
    		if((n / x) == (n % x)) {
    			sum += x;
    		}
    	}

    	if(i * i == n) {
    		continue;
    	}

    	if(i != 1) {
    		ll x = i - 1;
    		if((n / x) == (n % x)) {
    			sum += x;
    		}
    	}
    }

    cout << sum << "\n";
	return 0;
}

Measured memory_bytes: 256
N = gets.to_i

N.times do
  data = gets.split.map(&:to_i)

  b, c = [], []
  failure = false

  data.each do |num|
    if b.empty? || num > b[0]
      b.unshift(num)
    else
      if c.empty? || num > c[0]
        c.unshift(num)
      else
        failure = true
        break
      end
    end
  end

  if failure
    puts 'NO'
  else
    puts 'YES'
  end
end

Measured memory_bytes: 8468
#include<iostream>
#include<algorithm>
using namespace std;
const int inf = 0x7f7f7f7f;
const int MAXN = 1e6+1000;
const int MAXK = 1e6+1000;
inline int read() { //快读
	char ch = getchar();
	int x = 0, f = 1;
	while(ch < '0' || ch > '9') {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while('0' <= ch && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}
inline int _max(int x1,int x2) { //取最大值
	return x1>x2 ? x1 : x2;
}
struct _date {
	int L,R,ad; //左右边界及原位置（因为我们要离线排序后处理）
} a[MAXN];
int sum[MAXN],ans[MAXN],nxt[MAXN],head[MAXK],n,m,mx,num[MAXN];
inline int lowbit(int x) {
	return x&(-x); //树状数组lowbit
}
inline void add(int x,int v) {
	for(; x <= n; x+= lowbit(x)) {
		sum[x]+= v;
	}
	//树状数组更新操作
}
inline int _count(int x) {
	int tot = 0;
	for(; x; x-= lowbit(x)) {
		tot+= sum[x];
	}
	return tot;
	//树状数组查询操作
}
inline bool cmp(const _date x1,const _date x2) { //sort函数的cmp
	return x1.L==x2.L ? x1.R<x2.R : x1.L<x2.L;
}
void func() {
	n = read();m = read();
	for(int i = 1; i <= n; i++) {
		num[i] = read();
	}
	for(int i = n; i >= 1; i--) {
		nxt[i] = head[num[i]];
		head[num[i]] = i;
		mx = _max(mx,num[i]);
	}

	for(int i = 1; i <= m; i++) {
		a[i].L = read();
		a[i].R = read();
		a[i].ad = i; //存储初始位置
	}
	sort(a+1,a+m+1,cmp); //按R排序
	for(int i = 1; i <= mx; i++) {
		if(head[i]) {
			add(head[i],1); //打标记
		}
	}
	int now = 1;
	for(int i = 1; i <= m; i++) {
		while(now < a[i].L) {
			if(nxt[now]){
				add(nxt[now],1);
			}
			now++;
		}
		ans[a[i].ad] = _count(a[i].R)-_count(a[i].L-1); //按询问编号存储每组询问的结果
	}
	for(int i = 1; i <= m; i++){
		printf("%d\n",ans[i]);
	}
	return;
}
int main() {
	func();
	return 0;
}


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

int main() {
  int n, k;
  string s;
  cin >> n >> k >> s;
  if(s.at(k - 1) == 'A') s.at(k - 1) = 'a';
  if(s.at(k - 1) == 'B') s.at(k - 1) = 'b';
  if(s.at(k - 1) == 'C') s.at(k - 1) = 'c';
  cout << s << endl;
}

Measured memory_bytes: 3628
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int main(){
	char a[1500];
	cin.getline(a,1500);
	int len = strlen(a);
	for(int i=0;i<len;i++){
		if(a[i]>='a'&&a[i]<='z')
			printf("%c",a[i]-32);
		else if(a[i]>='A'&&a[i]<='Z')
			printf("%c",a[i]+32);
		else
			printf("%c",a[i]);
	}
	printf("\n");
	return 0;
} 


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

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    pair<int, int> ar[n];
    int id[n];
    for (int i = 0; i < n; i++) {
        cin >> ar[i].first >> ar[i].second;
        id[i] = i;
    }
    double avg = 0;
    int cnt = 0;
    do {
        for (int i = 0; i < n - 1; i++) {
            avg += sqrt(pow(ar[id[i]].first - ar[id[i + 1]].first, 2) + pow(ar[id[i]].second - ar[id[i + 1]].second, 2));
        }
        cnt++;
    } while (next_permutation(id, id + n));
    avg /= cnt;
    cout << fixed << setprecision(10) << avg << '\n';
    return 0;
}

Measured memory_bytes: 256
def day(x,y):
	start=0
	if x==2 or x==8 :
		start=0
	elif x==3 or x==11:
		start=1
	elif x==6:
		start=2
	elif x==9 or x==12:
		start=3
	elif x==1 or x==4 or x==7:
		start=4
	elif x==10:
		start=5
	elif x==5:
		start=6 



	day=(start+y)%7
	if day==1:
		return "Sunday"
	elif day==2:
		return "Monday"
	elif day==3:
		return "Tuesday"
	elif day==4:
		return "Wednesday"
	elif day==5:
		return "Thursday"
	elif day==6:
		return "Friday"
	else:#0
		return "Saturday"


while True:	
	x,y=map(int,input().split())
	if x==y==0:
		break
	print(day(x,y))

Measured memory_bytes: 7672
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <utility>
#include <iomanip>

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

using namespace std;

typedef pair<int, int> P;

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

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

    vector<int> t(n), a(n);
    rep(i, n) cin >> t[i];
    rep(i, n) cin >> a[i];

    if(t[n-1] != a[0]){
        cout << 0 << endl;
        return 0;
    }

    vector<int> h(n, -1);
    h[0] = t[0];
    for(int i = 1; i < n; i++){
        if(t[i] > t[i-1]){
            h[i] = t[i];
        }
    }

    if(h[n-1] != -1 && h[n-1] != a[n-1]){
        cout << 0 << endl;
        return 0;
    }

    h[n-1] = a[n-1];
    for(int i = n-2; i >= 0; i--){
        if(a[i] > a[i+1]){
            if(t[i] < a[i]){
                cout << 0 << endl;
                return 0;
            }
            if(h[i] != -1 && h[i] != a[i]){
                cout << 0 << endl;
                return 0;
            }
            h[i] = a[i];
        }
    }

    int ans = 1;
    int x = h[0];
    int cnt = 0;
    rep(i, n){
        if(h[i] != -1){
            int p = min(x, h[i]);
            rep(j, cnt){
                ans = ans * p % MOD;
            }
            x = h[i];
            cnt = 0;
        }else{
            cnt++;
        }
    }
    cout << ans << endl;
    return 0;
}


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

void swap(int& a, int& b)
{
  int tmp = a;
  a = b;
  b = tmp;
}

int main()
{
  int a, b, c;
  cin >> a >> b >> c;

  if(a > b)
    swap(a, b);
  if(a > c)
    swap(a, c);
  if(b > c)
    swap(b, c);

  cout << a << " " << b << " " << c << endl;
  return 0;
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
using namespace std;
const long long int INF = 1e18;
const long long int MOD = 1e9+7;

typedef pair<ll, ll> pairs;
typedef vector<pairs> p;

struct edge{
    ll to, cost;
};


ll gcd(ll a,ll b){
    if(b == 0){
        return a;
    }else{
        return gcd(b, a%b);
    }
}

ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}

ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

// 素数
vector<bool> IsPrime;
void sieve(size_t max){
    if(max+1 > IsPrime.size()){
        IsPrime.resize(max+1,true);
    } 
    IsPrime[0] = false;
    IsPrime[1] = false;

    for(size_t i=2; i*i<=max; ++i){
        if(IsPrime[i]){
            for(size_t j=2; i*j<=max; ++j){
                IsPrime[i*j] = false;
            }
        }
    }
}

// べき乗の余り
ll modpow(ll a, ll n){
    ll res = 1;
    while(n){
        if(n & 1){
            res = res * a % MOD;
        }
        a = a * a % MOD;
        n = n >> 1;
    }
    return res;
}

// コンビネーション
ll MAXN = 2e5+10;
vector<ll> inv(MAXN);
ll nCk(ll n, ll k) {
	ll res = 1;
	for(ll i = 1; i <= k; i++) {
		res = res*(n-i+1) % MOD;
	}
 
	for(ll i = 1; i <= k; i++) {
		res = res*inv[i] % MOD;
	}
	return res;
}

// 回文
bool kai(string S){
    bool flag = true;
    for(ll i=0;i<S.size()/2;++i){
        if(S[i] != S[S.size()-i-1]){
            flag = false;
            break;
        }
    }
    return flag;
}
// ---------------------------------------------

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

    if(n == k){
        for(ll i=0;i<n;++i){
            if(i != 0){
                cout<<' ';
            }
            cout<<s;
        }
        cout<<endl;
    }else if(s == 1){
        for(ll i=0;i<k;++i){
            if(i != 0){
                cout<<' ';
            }
            cout<<s;
        }
        for(ll i=0;i<n-k;++i){
            cout<<' '<<5;
        }
        cout<<endl;
    }else{
        for(ll i=0;i<k+1;++i){
            if(i != 0){
                cout<<' ';
            }
            if(i % 2 == 0){
                cout<<s - 1;
            }else{
                cout<<1;
            }
        }
        for(ll i=0;i<n-k-1;++i){
            cout<<' '<<1987681;
        }
        cout<<endl;
    }

    return 0;
}

Measured memory_bytes: 4624
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
using ll = long long;
const double INF = 1ll << 62;

int main() {
  ll xs, ys, xt, yt;
  cin >> xs >> ys >> xt >> yt;
  int N;
  cin >> N;
  N += 2;
  vector<ll> x(N), y(N), r(N);
  x[0] = xs; y[0] = ys; r[0] = 0;
  x[1] = xt; y[1] = yt; r[1] = 0;
  for (int i = 2; i < N; i++) {
    cin >> x[i] >> y[i] >> r[i];
  }
  vector<vector<pair<int, double>>> G(N);
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      double dx = x[i] - x[j];
      double dy = y[i] - y[j];
      double d = max(0.0, sqrt(dx * dx + dy * dy) - r[i] - r[j]);
      G[i].emplace_back(j, d);
    }
  }
  vector<double> dist(N, INF);
  priority_queue<pair<double, int>> q;
  q.emplace(0, 0);
  dist[0] = 0;
  while (!q.empty()) {
    auto p = q.top(); q.pop();
    int v = p.second;
    for (auto e: G[v]) {
      int u = e.first;
      double c = e.second;
      if (dist[v] + c < dist[u]) {
        dist[u] = dist[v] + c;
        q.emplace(-dist[u], u);
      }
    }
  }
  printf("%.10f\n", dist[1]);
  return 0;
}


Measured memory_bytes: 22524
#include <bits/stdc++.h>
using namespace std;
int main() {
 int N,T,A;
 cin>>N>>T>>A;
 double min=10000000;
 int answer=0;
 vector<int>data(N);
 for(int i=0; i<N; i++){
    cin>>data.at(i);
    int g=data.at(i);
    double h=(abs(A-(T-0.006*g)));
    if(min>h){
        min=h;
        answer=i+1;
    }
 }
 cout<<answer<<endl;

 }

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

const int di[4] = {1, 0, -1, 0};
const int dj[4] = {0, 1, 0, -1};

int main(){
    int H, W;
    cin >> H >> W;

    vector<string> field(H);
    
    for(int i = 0; i < H; i++) cin >> field[i];

    vector<vector<int>> dist(H, vector<int>(W, -1));
    dist[0][0] = 1;
    
    vector<vector<int>> prev_i(H, vector<int>(W, -1));
    vector<vector<int>> prev_j(H, vector<int>(W, -1));

    queue<pair<int, int>> que;
    que.push(make_pair(0, 0));

    while(!que.empty()){
        pair<int, int> current_pos = que.front();
        int i = current_pos.first;
        int j = current_pos.second;
        que.pop();

        for(int d = 0; d < 4; d++){
            int next_i = i + di[d];
            int next_j = j + dj[d];
            if(next_i < 0 || next_i >= H || next_j < 0 || next_j >= W) continue;
            if(field[next_i][next_j] == '#') continue;

            if(dist[next_i][next_j] == -1){
                que.push(make_pair(next_i, next_j));
                dist[next_i][next_j] = dist[i][j] + 1;
                prev_i[next_i][next_j] = i;
                prev_j[next_i][next_j] = j;
            }
        }
    }

    if(dist[H-1][W-1] == -1) cout << -1 << endl;
    else{
        int cnt = 0;
        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
                if(field[i][j] == '#') cnt++;
            }
        }
        cout << H*W - cnt - dist[H-1][W-1] << endl;
    }
}

Measured memory_bytes: 256
//Ankit Verma
//Chandigarh University
//verma_ankit484( handle on cp sites)
//verma.ankit484@gmail.com

#include<bits/stdc++.h>
typedef long long ll;

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	#ifdef AV
	freopen("int.txt", "r", stdin);
	#endif
	ll n,k;
	cin>>n>>k;
	if(k>=n)
		k=n-1;
	vector<ll> vc(n);
	for(ll i=0; i<n; i++){
		cin>>vc[i];
	}
	vector<ll> dp(n, INT_MAX);
	dp[0]=0;
	dp[1]=abs(vc[1]-vc[0]);
	for(ll i=2; i<k; i++)
		dp[i]=abs(vc[i]-vc[0]);
	for(ll i=k; i<n; i++){
		for(ll j=1; j<=k; j++){
			if(i-j<0) break;
			dp[i]=min(dp[i], dp[i-j]+abs(vc[i]-vc[i-j]));
		}
	}
	cout<<dp[n-1]<<"\n";
	return 0;
}


Measured memory_bytes: 1792
#include<cstdio>
using ull = unsigned long long;
ull dp[41][2], bit[40];

int main(){
    ull N, K;
    scanf("%llu %llu", &N, &K);
    for (size_t i = 0; i < N; i++){
        ull tmp;
        scanf("%llu", &tmp);
        for (size_t j = 0; j < 40; j++){
            bit[j] += tmp>>j&1;
        }
    }
    K++;
    unsigned digit[40], highest_bit = 0;
    for (size_t i = 0; i < 40; i++){
        digit[i] = K>>i&1;
        if(digit[i]) highest_bit = i;
    }
    ull tmp;
    for (size_t i = 39; i > highest_bit; i--){
        dp[i][0] = dp[i+1][0] + (1ULL<<i)*bit[i];
    }
    dp[highest_bit][0] = dp[highest_bit+1][0] + (1ULL<<highest_bit)*(N - bit[highest_bit]);
    dp[highest_bit][1] = dp[highest_bit+1][0] + (1ULL<<highest_bit)*bit[highest_bit];
    for (int i = highest_bit-1; i >= 0; i--){
        for (size_t j = 0; j < 2; j++){
            for (size_t k = 0; k <= (j ? 1 : digit[i]); k++){
                if(tmp = dp[i+1][j] + (1ULL<<i)*(k ? N - bit[i] :bit[i]); dp[i][j || k < digit[i]] < tmp) dp[i][j || k < digit[i]] = tmp;
            }
        }
    }
    printf("%llu\n", dp[0][1]);    
	return 0;
}

Measured memory_bytes: 1732
#include <stdio.h>

int main(void) {
  int n,i,j,num1[36],num2[36],nchange,min,minpoint,count;
  char mar1[36],mar2[36],mchange;
  scanf("%d",&n);
  for(i = 0; i < n; i++){
    scanf(" %c %d",&mar1[i],&num1[i]);
    num2[i] = num1[i];
    mar2[i] = mar1[i];
  }
  for(i = 0; i < n; i++){
    for(j = n - 1; j >= i + 1; j--){
      if(num1[j] < num1[j - 1]){
        nchange = num1[j];
        num1[j] = num1[j - 1];
        num1[j - 1] = nchange;
        mchange = mar1[j];
        mar1[j] = mar1[j - 1];
        mar1[j - 1] = mchange;
      }
    }
  }
  for(i = 0; i < n; i++){
    if(i != 0)printf(" ");
    printf("%c%d",mar1[i],num1[i]);
  }
  printf("\nStable\n");

  for(i = 0; i < n; i++){
    minpoint = i;
    min = 999;
    for(j = i; j < n; j++){
      if(min > num2[j]){
        min = num2[j];
        minpoint = j;
      }
    }
    nchange = num2[i];
    num2[i] = num2[minpoint];
    num2[minpoint] = nchange;
    mchange = mar2[i];
    mar2[i] = mar2[minpoint];
    mar2[minpoint] = mchange;
  }
  for(i = 0; i < n; i++){
    if(i != 0)printf(" ");
    printf("%c%d",mar2[i],num2[i]);
  }

  for(i = 0; i < n; i++)if(mar1[i] == mar2[i])count++;
  if(count == n)printf("\nStable\n");
  else printf("\nNot stable\n");
  return 0;
}


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

using namespace std;

const int N = 3e3 + 10;

int dp[N];
pair<int, int> dish[N];
int n, t;

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

  cin >> n >> t;
  for (int i = 0; i < n; ++i) {
    cin >> dish[i].first >> dish[i].second;
  }

  sort(dish, dish+n);

  int ans = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < t; ++j) {
      ans = max(ans, dp[j] + dish[i].second);
    }
    for (int j = t-1; j >= dish[i].first; --j) {
      dp[j] = max(dp[j], dp[j-dish[i].first] + dish[i].second);
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
def s():
 def b(M,x,y,n=1):
  M[x][y]=0;a=n
  if M[x-1][y]:
   t=b(M,x-1,y,n+1)
   if a<t:a=t
  if M[x][y-1]:
   t=b(M,x,y-1,n+1)
   if a<t:a=t
  if M[x+1][y]:
   t=b(M,x+1,y,n+1)
   if a<t:a=t
  if M[x][y+1]:
   t=b(M,x,y+1,n+1)
   if a<t:a=t
  M[x][y]=1
  return a
 for e in iter(input,'0'):
  n,m=int(e),int(input())
  P=[[0]*(n+2)for _ in[0]*(m+2)]
  for i in range(m):P[i+1][1:-1]=map(int,input().split())
  a=0
  for i in range(1,m+1):
   for j in range(1,n+1):
    if P[i][j]:
     t=b(P,i,j)
     if a<t:a=t
  print(a)
if'__main__'==__name__:s()


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

#include <iostream>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <stdint.h>
#include <string.h>

//#define _USE_MATH_DEFINES
//#include <math.h>

#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <string>

#include <algorithm>
#include <functional>
#include <bitset>
#include <functional>
#include <chrono>
#include <random>
#define sqr(x) (x) * (x)

typedef unsigned int u32;
typedef int i32;
typedef unsigned long long int u64;
typedef long long int i64;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;
using namespace std::chrono;

const i64 mod = 1000000007ll;
const i64 smod = 998244353ll;
const i64 inf = 1'000'000'000'000'000'000ll + 7;

const double eps = 1e-8;

const i64 MAXN = 100'000 + 6;

i64 n, k;

i64 binpow(i64 a, i64 p) {
    a = a % mod;
    if (p == 0) {
        return 1;
    }
    if (p == 1) {
        return a;
    }
    i64 t = binpow(a, p / 2);
    i64 r = t * t;
    r %= mod;
    if (p % 2) {
        r *= a;
        r %= mod;
    }
    return r;
}

i64 g[MAXN];


int main(int argc, char* argv[]) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed);

    cin >> n >> k;
    for (i64 i = 1; i <= k; i++) {
        g[i] = binpow(k / i, n);
    }

    for (i64 i = k; i >= 1; i--) {
        for (i64 j = 2; i * j <= k; j++) {
            g[i] -= g[i * j];
            g[i] = (g[i] + mod) % mod;
        }
    }

    i64 R = 0;
    for (i64 i = 1; i <= k; i++) {
        R += g[i] * i;
        R %= mod;
    }

    cout << R << endl;

    return 0;
}

Measured memory_bytes: 4364
#include <bits/stdc++.h>
using namespace std;
int main(void){
    
    char c;
    int k[26]={};
    
    while(cin >> c){
        c=tolower(c);
        c -= 'a';
        k[(int)c]++;
    }
    for(int i=0;i<26;i++){
        cout << (char)(i+'a') <<" : "<< k[i] << endl; 
    }
    
    
}



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

int main()
{
    int N, M;
    std::cin >> N >> M;

    int even = 0;
    int odd = 0;

    if (N <= 1)
        even = 0;
    else
        even = N * (N - 1) / 2;

    if (M <= 1)    
        odd = 0;
    else
        odd = M * (M - 1) / 2;

    std::cout << even + odd << std::endl;

    return 0;
}

Measured memory_bytes: 256