akhauriyash/Code-Regression huggingface dataset:
import queue

import sys
sys.setrecursionlimit(10000)

N, M = map(int, input().split())
S = set(range(N))

to = [[] for _ in range(N)]
for _ in range(M):
    a, b = [int(x)-1 for x in input().split()]
    to[a].append(b)

visit = [0] * N
def DFS(p, n):
    if visit[p] != 0:
        return visit[p]
    else:
        visit[p] = n + 1
        for i in to[p]:
            r = DFS(i, n + 1)
            if r > 0:
                return r
        visit[p] = -1
        return -1

for i in range(N):
    r = DFS(i,0)
    if r > 0:
        for j in range(N):
            if visit[j] < r:
                S.discard(j)
        for j in range(N):
            if j in S:
                for k in to[j]:
                    if k in S:
                        if visit[k] < visit[j]:
                            for l in range(N):
                                if visit[l] < visit[k] or visit[l] > visit[j]:
                                    S.discard(l)
                        else:
                            for l in range(N):
                                if visit[l] > visit[j] and visit[l] < visit[k]:
                                    S.discard(l)
        print(len(S))
        for j in list(S):
            print(j+1)
        break
    if i == N-1:
        print(-1)

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

def main():
    n = int( input() )
    A = list( map( int , input().split() ) )
    A_sum = sum(A)
    A_sum -= A[0]
    ans = 0

    for i in range( n - 1 ) :
        a_i = A[i]
        ans += ( (A_sum * a_i) % (10 ** 9 + 7 ) )
        A_sum -= A[ i + 1 ]
        ans %= ( 10 ** 9 + 7 )

    print(ans)



main()

Measured memory_bytes: 31608
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define rep(i,s,e) for(int i = (s);i <= (e);i++)

typedef long long ll;

int n;
ll x[100010];

ll a;
ll b;

ll len[100010];
int main()
{
	cin >> n;
	cin >> a >> b;
	rep(i,0,n - 1)
	{
		cin >> x[i];
		if(x > 0)
		{
			len[i] = x[i] - x[i - 1];
		}
		
	}

	vector<ll> dp(n,1e18);

	dp[0] = 0;

	rep(i,1,n - 1)
	{
		dp[i] = dp[i - 1];
		dp[i] += min(len[i] * a , b);
	}

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

	return 0;
}


Measured memory_bytes: 2560
import java.util.*;
public class Main {
    static int N, A, B, C;
    static int[] l;
    static final int INF = 1000000000;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        A = sc.nextInt();
        B = sc.nextInt();
        C = sc.nextInt();
        l = new int[N];
        for (int i = 0; i < N; i++) {
            l[i] = sc.nextInt();
        }
        System.out.println(dfs(0, 0, 0, 0));
        sc.close();
    }
    static int dfs(int i, int a, int b, int c) {
        if (i == N) {
            if (a == 0 || b == 0 || c == 0) {
                return INF;
            }
            return Math.abs(a - A) + Math.abs(b - B) + Math.abs(c - C);
        }

        int res = dfs(i + 1, a, b, c);
        if (a == 0) {
            res = Math.min(res, dfs(i + 1, a + l[i], b, c));
        } else {
            res = Math.min(res, dfs(i + 1, a + l[i], b, c) + 10);
        }
        if (b == 0) {
            res = Math.min(res, dfs(i + 1, a, b + l[i], c));
        } else {
            res = Math.min(res, dfs(i + 1, a, b + l[i], c) + 10);
        }
        if (c == 0) {
            res = Math.min(res, dfs(i + 1, a, b, c + l[i]));
        } else {
            res = Math.min(res, dfs(i + 1, a, b, c + l[i]) + 10);
        }

        return res;
    }
}

Measured memory_bytes: 24784
import sys, collections
def single_input(F): return F.readline().strip("\n")
def line_input(F): return F.readline().strip("\n").split()

def bfs(initialnode, edge, nodeNum):
    visited = [False] * nodeNum
    dist = []
    search_que = collections.deque()
    search_que.append((0, initialnode))
    count = 0
    while count < nodeNum:
        nowDist, nowNode = search_que.popleft()
        if not visited[nowNode]:
            visited[nowNode] = True
            dist.append((nowDist, nowNode))
            count += 1
            for nextNode in edge[nowNode]:
                if not visited[nextNode]:
                    search_que.append((nowDist+1, nextNode))
    return dist[-1]

def solve():
    F = sys.stdin
    N = int(single_input(F))
    Edge = [[] for i in range(N)]
    for _ in range(N-1):
        a, b = map(int, line_input(F))
        Edge[a-1].append(b-1)
        Edge[b-1].append(a-1)

    most_far_from_zero = bfs(0, Edge, N)
    tree_d, node_on_otherside = bfs(most_far_from_zero[1], Edge, N)

    if tree_d % 3 == 1: print("Second")
    else: print("First")
    return 0
  
if __name__ == "__main__":
    solve()

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

int M, N;
pair<int,ll> a[100005];

bool cmp(pair<int,ll> t1, pair<int,ll> t2){
	return t1.second < t2.second;
}

int main(){
	cin >> N >> M;
	for (int i = 1; i <= N; ++i){
		cin >> a[i].second >> a[i].first;
	}
	sort(a+1, a+N+1, cmp);
	ll c = 0;
	for (int i = 1; M > 0 && i <= N; ++i){
		c += a[i].second * (min(M, a[i].first));
		M -= a[i].first;
	}
	cout << c << '\n';
	return 0;
}

Measured memory_bytes: 1792
use std::io::prelude::*;

fn input<T: std::str::FromStr>() -> T {
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

fn main() {
    let n: usize = input();
    let d: usize = input();
    let x: Vec<Vec<i32>> = (0..n).map(|_| (0..d).map(|_| input()).collect()).collect();

    let mut ans = 0;
    for i in 0..n {
        for j in 0..i {
            let s: i32 = (0..d)
                .map(|d| i32::abs(x[i][d] - x[j][d]) * i32::abs(x[i][d] - x[j][d]))
                .sum();
            let t = (f64::sqrt(s as f64) + 0.01) as i32;
            if s == t * t {
                ans += 1;
            }
        }
    }

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <iostream>
#include <string>
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <algorithm>
#include <ctime>
#include <vector>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;

#define PI 3.14159265358979323846264338327950L

long double res;

int main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    long double N, K;
    cin >> N >> K;
    vector<long double> p(N);
    vector<long double> add(N, 0);
    long double max = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> p[i];
        p[i]++;
        p[i] /= 2;
    }
    add[0] = p[0];
    for (int i = 1; i < N; i++)
    {
        add[i] = p[i] + add[i - 1];
    }
    if(N==K){
        cout << fixed << setprecision(15) << add[N - 1] << endl;
        return 0;
    }
    for (int i = 0; i <= N - K; i++)
    {
        if (max < add[i + K] - add[i])
        {
            max = add[i + K] - add[i];
        }
    }
    cout << fixed << setprecision(15) << max << endl;
    return 0;
}

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

bool ok(int n) {
    for (int i = 0; i < 130; i++) {
        if (i*i == n) return true;
    }
    return false;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n, d, res = 0;
    cin >> n >> d;
    int x[n][d];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < d; j++) {
            cin >> x[i][j];
        }
    }
    for (int i = 0; i < n-1; i++) {
        for (int j = i+1; j < n; j++) {
            int calc = 0;
            for (int k = 0; k < d; k++) {
                calc += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
            }
            if (ok(calc)) res++;
        }
    }
    cout << res << endl;
}









Measured memory_bytes: 256
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <bitset>
#include <cstdlib>

using namespace std;

typedef long long int ll;
typedef vector<ll> vl;
typedef vector<string> vs;

#define MAX(a,b) ((a)>(b) ? (a) : (b))
#define MIN(a,b) ((a)<(b) ? (a) : (b))
#define ABS(a) ((a)>0 ? (a) : (a * -1))


int main(){
	string a, b, c;
	char d, e, f;
	cin >> a >> b >> c;

	d = toupper(a[0]);
	e = toupper(b[0]);
	f = toupper(c[0]);

	cout << d  << e << f << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const LL MOD = 1000000007LL;
bool b[100001]={false};
int num[100001];
LL fact[100001];
LL inv[100001];
LL inv_fact[100001];
LL mod_pow(LL x, LL a) {
    if (a == 0) return 1;
    if (a % 2 == 0) {
        LL ret = mod_pow(x, a / 2);
        return (ret*ret) % MOD;
    }
    else {
        return (x*mod_pow(x, a - 1)) % MOD;
    }
}
LL comb(LL n, LL k) {
    if (n < k) return 0;
    LL ans = (fact[n] * inv_fact[k]) % MOD;
    ans = (ans*inv_fact[n - k]) % MOD;
    return ans;
}
int main(){
    int n,dup[2];
    cin>>n;
    for(int i=0;i<=n;i++){
        int a;
        cin>>a;
        num[i]=a;
        if(!b[a-1])b[a-1]=true;
        else {
            dup[1]=i;
            break;
        }
    }
    for(int i=0;i<dup[1];i++){
        if(num[i]==num[dup[1]])dup[0]=i;
    }
    fact[0] = 1;
    inv_fact[0] = 1;
    for(int i=1;i<n+1;i++){
        inv[i] = mod_pow(i, MOD - 2);
        fact[i] = (fact[i - 1] * i) % MOD;
        inv_fact[i] = (inv_fact[i - 1] * inv[i]) % MOD;
    }
    int cen=dup[1]-dup[0]-1;
    cout<<n<<endl;
    for (int i=2; i<=n+1; i++) {
        LL sum=0;
        sum=(sum+comb(n-1, i))%MOD;
        sum=(sum+comb(n-1, i-2))%MOD;
        sum=(sum+2*comb(n-1, i-1))%MOD;
        sum=(sum-comb(n-cen-1,i-1)+MOD)%MOD;
        cout<<sum%MOD<<endl;
    }
}

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

int main(){
  int l1, l2;
  char s[100];
  cin >> l1 >> l2;
  if(l1<1 || l1>5 || l2<1 || l2>5){
    cout << "No" << endl;
    return 0;
  }
  cin >> s;
  for(int i=0; i<l1; ++i){
    char c = s[i];
    if( c < '0' || c > '9'){
      cout << "No" << endl;
      return 0;
    }
  }
  if (s[l1] != '-'){
    cout << "No" << endl;
    return 0;
  }
  for(int i=l1+1; i<l1+l2+1; ++i){
    char c = s[i];
    if( c < '0' || c > '9'){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static Input;

public class Prog
{
    private const int INF = 1000000007;
    private const long INFINITY = 9223372036854775807;
    public static void Main()
    {
        int A = NextInt();
        int B = NextInt();
        int C = NextInt();
        Console.WriteLine((A == B && B == C?"Yes":"No"));
    }
}

public class Input
{
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}


Measured memory_bytes: 11220
use std::io;

fn main() {
    let mut n = String::new();
    io::stdin().read_line(&mut n).expect("Failed to read line.");
    
    let mut line = String::new();
    io::stdin().read_line(&mut line).expect("Failed to read line.");
    let nums = line.trim().split(' ').flat_map(str::parse::<u32>).collect::<Vec<_>>();

    let mut min = 1000000000;
    let mut max = 0;
    for a in nums {
        if a > max {
            max = a;
        }
        if a <= min {
            min = a;
        }
    }
    println!("{}", max - min);
}


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

int main()
{
	int n;
	cin >> n;
	vector<ll> a(n),b(n),c(n);
	for(int i=0;i<n;i++)
		cin >> a[i] >> b[i] >> c[i];

	vector<vector<ll> > dp(3, vector<ll>(n));
	dp[0][0] = a[0];
	dp[1][0] = b[0];
	dp[2][0] = c[0];

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

	ll ans = dp[0][n-1];
	ans = max(ans,dp[1][n-1]);
	ans = max(ans, dp[2][n-1]);
	cout << ans << endl;


	return 0;
}

Measured memory_bytes: 5760
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using E = tuple<ll, int, ll>;
const ll inf = numeric_limits<ll>::max()/3;
const ll mod = 1e9 + 7;

int main(void){
  int n;
  scanf("%d", &n);
  if(n == 2) {
    ll a,b;
    scanf("%lld %lld", &a, &b);
    printf("%lld\n", max(a,b) - min(a,b));
    printf("%lld %lld\n", max(a,b), min(a,b));
    return 0;
  }
  
  vector< ll > plus;
  vector< ll > minus;
  for(int i = 0;i < n;++i){
    ll tmp;
    scanf("%lld", &tmp);
    if(tmp >= 0) plus.push_back(tmp);
    else minus.push_back(tmp);
  }
  
  vector< P > res;
  sort(plus.begin(),plus.end());
  sort(minus.begin(), minus.end());
  if(plus.empty()){
    ll acc = minus[n-1];
    for(int i = 0;i < n-1;++i){
      res.push_back(P(acc,minus[i]));
      acc -= minus[i];
    }
    printf("%lld\n", acc);
  }else if(minus.empty()){
    ll acc = plus[0] - plus[n-1];
    res.push_back(P(plus[0], plus[n-1]));
    for(int i = 1;i < n-2;++i){
      res.push_back(P(acc,plus[i]));
      acc -= plus[i];
    }
    res.push_back(P(plus[n-2], acc));
    acc = plus[n-2] - acc;
    printf("%lld\n",acc);
  }else{
    for(int i = 1;i < (int)plus.size();++i){
      res.push_back(P(minus[0],plus[i]));
      minus[0] -= plus[i];
    }
    for(int i = 1;i < (int)minus.size();++i){
      res.push_back(P(plus[0],minus[i]));
      plus[0] -= minus[i];
    }
    res.push_back(P(plus[0],minus[0]));
    printf("%lld\n", plus[0] - minus[0]);
  }
  
  for(P p : res){
    printf("%lld %lld\n", p.first, p.second);
  }
  
  return 0;
}


Measured memory_bytes: 5104
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>
#define INF 2000'000'000
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef tree<int, null_type,less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	//freopen("in", "r", stdin);//freopen("out", "w", stdout);
	int n;
	cin >> n;
	vector < long double > p(n+1);
	for(int i = 1; i <= n; i++)
		cin >> p[i];
	
	vector < vector < long double > > dp(n+1, vector < long double > (n+1));
	dp[0][0] = 1;
	// dp[cnt][i] = probability of getting cnt heads after using first i coins
	for(int cnt = 0; cnt <= n; cnt++){
		for(int i = 1; i <= n; i++){
			dp[cnt][i] = dp[cnt][i-1] * (1-p[i]);
			if(cnt)
				dp[cnt][i] += dp[cnt-1][i-1] * p[i];
		}
	}
	double ans = 0;
	for(int i = n; i * 2 > n; i--){
		ans += dp[i][n];
	}
	cout << fixed << setprecision(9) << ans << endl;
	return 0;
}


Measured memory_bytes: 144244
#include <functional>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;

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

    ll a, b, k;
    cin >> a >> b >> k;

    if (a > k) {
        cout << a - k << ' ' << b << '\n';
    } else {
        cout << 0 << ' ' << max(0LL, b - (k - a)) << '\n';
    }

    return 0;
}

Measured memory_bytes: 888
x, k ,d = map(int, input().split())

x = abs(x)
y = k * d
ans = x + d
if(x > y):
    ans = min(ans , x - y)
else:
    mar = x % d
    if (x // d) % 2 == (k % 2):
        ans = min(ans , mar)
    else:
        ans = min(ans , abs(d - mar))
print(ans)


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

int main() {
	ll n,m,ans=0;
	cin>>n>>m;
	ll endt=0;
	for(ll i=0;i<n;i++){
		ll t;
		cin>>t;
		ans+=m;
		if(t<endt){
			ans-=endt-t;
		}
		endt=t+m;
	}
	cout <<ans;
}

Measured memory_bytes: 256
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif




#define int long long
#define rng(i,l,r) for(size_t i=(l);i<(r);++i)
#define rep(i,n) rng(i,0,n)
#define gnr(i,l,r) for(size_t i=(r)-1;i>=(l);i--)
#define per(i,b) gnr(i,0,b)
#define ALL(obj) (obj).begin(), (obj).end()   //1,2,3,...
#define rALL(obj) (obj).rbegin(), (obj).rend()//...,3,2,1

using namespace std;
//using ll = long long;


const int MOD = 1000000007;
const int INF = 1e18;

const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1,1,0,-1,-1,-1,0,1};
const int dy8[8] = {0,1,1,1,0,-1,-1,-1};

const double pi = acos(-1);



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


using Graph = vector<vector<int>>;



void solve(){
    
    // remove the bottom 3 lines when you submit this code.
    std::ifstream in("sample.txt");
    std::cin.rdbuf(in.rdbuf());

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

    
    int n; cin >> n;
    vector<double> v(n);
    rep(i,n) cin >> v[i];
    sort(ALL(v));
    
    
    double ans = 0;
    
    for (int i = 0; i < n-1; i++) {
        if(i==0){
            ans = (v[i]+v[i+1])/2;
        }else{
            ans = (ans + v[i+1])/2;
        }
    }
    
    cout << setprecision(10) << ans << endl;
    
    
}



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



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


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


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def main():
    A = [list(readnums()) for _ in range(3)]
    c = [[False] * 3 for _ in range(3)]
    N = readint()
    for i in range(N):
        a = readint()
        pos = [(x, y) for y, row in enumerate(A) for x, elem in enumerate(row) if A[x][y] == a]
        if pos:
            x, y = pos[0]
        else:
            continue
        c[x][y] = True

    if all(c[0]) or all(c[1]) or all(c[2]) or all([x[0] for x in c]) or all([x[1] for x in c]) or all([x[2] for x in c]) or all([x[i] for i, x in enumerate(c)]) or all([x[2 - i] for i, x in enumerate(c)]):
        print('Yes')
    else:
        print('No')


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#define rep(i,n) for(int i=0; i < (n); i++)
#define INF 1001001
using namespace std;
 
int main(){
  int n, count=1;
  vector<string> dict;
  cin >> n;
  string s;
  int flag=0;
  rep(i,n){
    cin >> s;
    dict.push_back(s);
  }
  sort(dict.begin(), dict.end());
  rep(i,n-1){
    if(dict[i]!=dict[i+1]) count++;
  }
  cout << count << endl;
  
  
}

Measured memory_bytes: 11640
import sys
input = sys.stdin.readline
N,M,Q = map(int,input().split())
LR = [tuple(map(int,input().split())) for i in range(M)]
PQ = [tuple(map(int,input().split())) for i in range(Q)]

imos = [[0]*(N+1) for _ in range(N+1)]
for l,r in LR:
    imos[l][r] += 1
for i in range(N+1):
    for j in range(N):
        imos[i][j+1] += imos[i][j]
for j in range(N+1):
    for i in range(N):
        imos[i+1][j] += imos[i][j]

ans = []
for p,q in PQ:
    p -= 1
    a = imos[q][q] + imos[p][p] - imos[p][q] - imos[q][p]
    ans.append(a)
print(*ans, sep='\n')

Measured memory_bytes: 49948
n,M =map(int,input().split())
s=0
t=1
list1=[]
list2=[]
u=0
if M==1:
    print("1 2")
else:    
    while s< M:
        while (t<=((n+1)//2)//2 and s<M):
            lis=t
            list1.append(lis)
            lis2=(n+1)//2+1-t
            list2.append(lis2)
            t+=1
            s+=1
        lis=(n+1)//2+1+u
        list1.append(lis)
        lis2=2*((n+1)//2)-1-u
        list2.append(lis2)
        u+=1
        s+=1
    for i in range(0,M):
        print(list1[i],list2[i])

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

const int N = 100005;

int n;
vector<int> G[N];
bool ans;

int dfs(int u, int p) {
	int cnt = 0;
	for (int v : G[u]) if (v != p) {
		int w = dfs(v, u); if (w == 0) ++cnt;
	}
	if (cnt <= 1) return cnt;
	else ans = true;
	return -1;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	if (n == 2) return printf("Second\n"), 0;
	for (int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		G[u].push_back(v); G[v].push_back(u);
	}

	int res = dfs(1, 0);
	if (res == 0) ans = 1; 

	printf(ans ? "First\n" : "Second\n");
}

Measured memory_bytes: 5888
/*There's a possibility*/
#define dbg(...) ; 
#define db(...) ; 
#include "bits/stdc++.h"
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define f(i,a,b) for(i=a;i<b;i++)
#define fr(i,a,b) for(i=a;i>=b;i--)
#define endl '\n'
#define tst cout<<'*';
#define ll long long int
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mod 1000000007
using namespace std;

ll dp[100][100005];

int main()
{
    fast;
    int n,k,i,j;
    cin>>n>>k;
    int ar[n];
    f(i,0,n)
        cin>>ar[i],dp[i][0]=1;
    f(j,0,ar[0]+1)
        dp[0][j]=1;

    f(i,1,n)
        f(j,1,k+1)
        {
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
            if(j>ar[i])
                dp[i][j]=(dp[i][j]-dp[i-1][j-ar[i]-1]+mod)%mod;
        }

    cout<<dp[n-1][k];
    //db(dp,0,n-1,0,k);
}

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

char a[22][22];
int n,m;

struct pos
{
	int x;
	int y;
	int step;
};

pos make_pos(int a,int b,int c)
{
	pos ret;
	ret.x=a;
	ret.y=b;
	ret.step=c;
	return ret;
}

int bfs(int sx,int sy,int ex,int ey)
{
	bool vis[n+2][m+2];
	for(int i=0;i<=n+1;i++)
		for(int j=0;j<=m+1;j++)
			if(a[i][j]=='#')
				vis[i][j]=true;
			else
				vis[i][j]=false;
				
	queue<pos> q;
	q.push(make_pos(sx,sy,0));
	vis[sx][sy]=true;
	
	int move[2][4]={{0,0,-1,1},
				   {-1,1,0,0}};
	
	while(!q.empty()){
		pos fr=q.front();
		q.pop();
		if(fr.x==ex && fr.y==ey)
			return fr.step;
			
		pos newpos;
		for(int i=0;i<4;++i){
			int nx=fr.x+move[0][i];
			int ny=fr.y+move[1][i];
			if(vis[nx][ny])
				continue;
			vis[nx][ny]=true;
			newpos=make_pos(nx,ny,fr.step+1);
			q.push(newpos);
		}
	}
}
int main()
{
	for(int i=0;i<22;i++)
		for(int j=0;j<22;j++)
			a[i][j]='#';
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	
	int maxv=0;
	
	for(int i1=1;i1<=n;i1++)
		for(int j1=1;j1<=m;j1++)
		{
			if(a[i1][j1]=='#')
				continue;
			for(int i2=1;i2<=n;i2++)
					for(int j2=1;j2<=m;j2++)
					{
						if(a[i2][j2]=='#')
							continue;
						if(i1==i2 && j1==j2)
							continue;
						maxv=max(maxv,bfs(i1,j1,i2,j2));
					}
		}
	cout<<maxv<<endl;
	return 0;
}

Measured memory_bytes: 256
c=0
n=int(input())
A_list=list(map(int,input().split()))
B_list=list(map(int,input().split()))
C_list=list(map(int,input().split()))
for i in range(0,n):
  c+=B_list[A_list[i]-1]
  if i==n-1:
    break
  if A_list[i]==(A_list[i+1]-1):
    c+=C_list[A_list[i]-1]
print(c)  

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<functional>
using namespace std;
#define ll long long int
#define ld long double
using namespace __gnu_pbds;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,
tree_order_statistics_node_update> in_set;
#define rep(n) for(ll i=0;i<(n);i++)
#define jrep(n) for(ll j=0;j<(n);j++)
#define all(a) (a).begin(), (a).end()
#define dpp(a) cout<<(a).first<<" "<<(a).second<<endl;
#define append push_back
#define mod 1000000007
#define ff first
#define ss second
#define ffast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fast ios::sync_with_stdio(0);
ll pw(ll x,ll y,ll p=mod){ll r=1; x=x%p;while(y>0){ if(y&1)r=(r*x)%p;
y=y>>1;x=(x*x)%p;} return r; } vector<ll> uniq(vector<ll> arr)
{vector<ll>brr;sort(all(arr));brr.append(arr[0]);
for(auto i:arr)if(brr.back()!=i)brr.append(i);return brr;}
 
void solve(){
    ll n,m; cin>>n>>m;
    vector<ll> arr(n); rep(n) cin>>arr[i]; sort(all(arr));
    ll le = n-m;
    if(le<=0){ cout<<"0\n"; return; }
    ll su=0;
    rep(le){ su+=arr[i]; }
    cout<<su<<endl;
}
 
int main(){
    ffast
    ll t=1;
    //cin>>t;
    rep(t) solve();
}
 
 
// *p.find_by_order(n) : nth value (0 indexed)
// p.order_of_key(7): index of 7 (0 indexed)


Measured memory_bytes: 1792
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <math.h>
#include <stack>
#include <climits>
#include <bitset>

using namespace std;
typedef long long ll;

//最小公倍数
ll gcd(ll x, ll y) {
  ll tmp = 0;
  if (x < y){
    tmp=x;
    x=y;
    y=tmp;
  }
  while (y > 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return x;
}

//最大公倍数
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}

//階乗
ll kaijo(ll k){
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum *= i;
        sum%=1000000000+7;
    }
    return sum;
}

//for(int i = ; i < ; i++){}


int main(){
  int a,b,c;
  cin>>a>>b>>c;
  cout<<c-min(a-b,c)<<endl;
  return 0;
}

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

using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;
typedef vector < vector<ll> > Mat;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int N;
bool flag[105];

int main(){
  cin >> N;
  for (int i = 1; i <= N; i++){
    int D1, D2; cin >> D1 >> D2;
    if (D1 == D2) flag[i] = true;
  }

  int cnt = 0;
  for (int i = 1; i <= N + 1; i++){
    if (cnt >= 3){
      Yes(); return 0;
    }
    if (flag[i]) cnt++;
    else cnt = 0;
  }
  No();


  return 0;
}



Measured memory_bytes: 3592
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <sstream>
#include <string>
using namespace std;

bool is_parindrome(string s) {
	string tmp = s;
	reverse(tmp.begin(), tmp.end());
	return s == tmp;
}

string itos(int n) {
	ostringstream os;
	os << n;
	return os.str();
}

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

	int n;
	cin >> n;

	int ans;
	for(int i = n;; --i) {
		if(is_parindrome(itos(i))) {
			ans = i;
			break;
		}
	}

	for(int i = n; (i - n) < (n - ans); ++i) {
		if(is_parindrome(itos(i))) {
			ans = i;
			break;
		}
	}

	cout << ans << endl;

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1224
#include <iostream>
  #include <complex>
  #include <vector>
  #include <string>
  #include <algorithm>
  #include <cstdio>
  #include <numeric>
  #include <cstring>
  #include <ctime>
  #include <cstdlib>
  #include <set>
  #include <map>
  #include <unordered_map>
  #include <unordered_set>
  #include <list>
  #include <cmath>
  #include <bitset>
  #include <cassert>
  #include <queue>
  #include <stack>
  #include <deque>
 #include <iomanip>
#include <fstream>
#include <climits>
 
  using namespace std;
   
 
//abcdefghijklmnopqrstuvwxyz
//ABCDEFGHIJKLMNOPQRSTUVWXYZ

  typedef long long ll;
  typedef long double lld;
  typedef unsigned long long ull;
  // int INF = INT_MAX;
  // ll mod = 1000000007;
  // lld PI = 3.141592653;


  int main()
  {
      ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
     ll a,b,c,d;
     cin>>a>>b>>c>>d;
     cout<<max({a*c, a*d, b*c, b*d});



}

Measured memory_bytes: 3104
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	long long a[n];
	for(int i=0;i<n;i++)
	{
		long long x,y,m;
		cin>>x>>y;
		long long t=sqrt(x*y-1);
		if(t*t>=x*y) t--;
		a[i]=t*2;
		if(t*(t+1)>=(x*y))
		a[i]--;
		if(t>=x)
		a[i]--;
		if(t>=y)
		a[i]--;
	}
	for(int i=0;i<n;i++)
	cout<<a[i]<<endl;
	return 0;
} 

Measured memory_bytes: 256
/********
*	????????????I
*********/	
/*********??¢?????´?????????
*	??????????????????????????????????????\????????¢???????????????4??¢???1??????????????????????????????
*	???????????´??¢?????????????????????????????§??????????????????
*********/

#include <stdio.h>
#include <iostream>
using namespace std;


int main(void)
{
	int dice[6]={0}; 		//?????????????????¢?????°???????????????????????????????????°??????????????????[0]????????¢
	int temp;	
	char sai[100];		//?????????????????¢?????????????????????????????????????????????
	
	for(int i=0; i< 6; i++){//????????????6??¢?????°?????\???
		cin >> dice[i];
	}
	
	cin >>sai ;		//?????????????§??????????????????\???
	
		for(int i = 0; sai[i]; i++){
		if(sai[i]=='S'){
			temp    = dice[4];
			dice[4] = dice[5];
			dice[5] = dice[1];
			dice[1] = dice[0];
			dice[0] = temp;				//??´??¢?????????dice[2][3]???????????????
		} else if(sai[i]=='N' ){
			temp    = dice[1];
			dice[1] = dice[5];
			dice[5] = dice[4];
			dice[4] = dice[0];
			dice[0] = temp;				//??´??¢?????????dice[2][3]???????????????
		} else if (sai[i]=='W'){
			temp    = dice[2];
			dice[2] = dice[5];
			dice[5] = dice[3];
			dice[3] = dice[0];
			dice[0] = temp ;			//??´??¢?????????dice[1][4]???????????????	
		}else if(sai[i]=='E'){
			temp    = dice[3];
			dice[3] = dice[5];
			dice[5] = dice[2];
			dice[2] = dice[0];
			dice[0] = temp;				//??´??¢?????????dice[1][4]???????????????	
		}
	}
	printf("%d\n",dice[0]);
	return 0;
}

Measured memory_bytes: 1148
import Data.List

main :: IO ()
main = do
  n <- read <$> getLine :: IO Int
  let (check,k) = notfind 1 n
  if check then putStrLn $ "No"
    else putStrLn "Yes" >> putStrLn (show k) >> subset 0 (k-1) 0 --

notfind :: Int -> Int -> (Bool,Int)
notfind count n = if 2*n == count*(count+1) then (False,count+1)
  else if 2*n < count*(count+1) then (True,count+1)
     else notfind (count+1) n

subset :: Int -> Int -> Int -> IO ()
subset n k iv = do
  if n == (k+1) then return () else do
    putStr $ (show k) ++ " "
    --putStr "loop1-> "
    loop1 n (k-n) (iv+(n*k-(n*(n-1))`div`2)) --iv+Σ(k-i)
    --putStr "loop2-> "
    loop2 n k iv
    putStrLn ""
    subset (n+1) k iv

loop1 n 0 iv = return ()
loop1 n k iv = do
  putStr $ (show (k+iv)) ++ " "
  loop1 n (k-1) iv

loop2 0 k iv = return ()
loop2 n k iv = do
  putStr $ (show (n+iv)) ++ " "
  loop2 (n-1) (k-1) (iv+k)


Measured memory_bytes: 2172
#include<bits/stdc++.h>
using namespace std;
#define For(i,n,k) for(int i=(n);i<(k);i++)
#define ALL(a)  (a).begin(),(a).end()
void Main(){
    long long N,cnt=0;cin>>N;
    vector<int> A(N),B(N);
    For(i,0,N) cin>>A[i]>>B[i];
    for(int i=N-1;i>-1;i--) if((A[i]+cnt)%B[i]) cnt+=(B[i]-(A[i]+cnt)%B[i]);
    cout<<cnt<<endl;
}
int main(){
    Main();
    return 0;
}

Measured memory_bytes: 1024
/*
AtCoder Beginner Contest 105 B - Cakes and Donuts
結果:
*/

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>

//#define DEBUG1
//#define DEBUG2
//#define DEBUGF

int main() {
	static int N, i, j, tmp = 0, ans;

	scanf("%d", &N);
	for (i = 0; i <= 100 / 4; i++) {
		for (j = 0; j <= 100 / 7; j++) {
			if (N == (4 * i + 7 * j)) {
				++tmp;
				continue;
			}
		}
	}
	if (tmp != 0) {
		printf("%s\n", "Yes");
	}
	else {
		printf("%s\n", "No");
	}

#ifdef DEBUGF
	getch();
#endif
	return 0;
}


Measured memory_bytes: 128
#include <stdio.h>
#define N 100
  
int main(){
  
  int i, j, n, min, minj, total=0;
  int A[N][N], flag[N], t[N];
  
  scanf("%d", &n);

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

  for(i = 0; i < n; i++){
    flag[i] = 0;
    t[i] = 2001;
  }

  t[0] = 0;
  
  for(i = 0; i < n - 1; i++){
    min = 2001;
    for(j = 0; j < n; j++){
      if(t[j] < min && flag[j] == 0){
	min = t[j];
	minj = j;
      }
    }

    flag[minj] = 1;
  
    for(j = 0; j < n; j++){
      if(A[minj][j] != -1 && A[minj][j] < t[j] && flag[j]==0){
	t[j] = A[minj][j];
      }
    }
  }
  
  for(i = 0; i < n; i++){
    total += t[i];
  }
  printf("%d\n", total);

  return 0;
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
struct edge{ll to,cost;};
const int inf = 1<<28;
const ll INF = 1LL<<53;
const int COMBMAX = 500005;
const ll MOD = 1e9+7;
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<n;++i)
#define repf(i,n) for(int i=0;i<=n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define eachdo(v, e) for(const auto& e : v)
#define all(v) (v).begin(), (v).end()
#define lower_index(v, e) (ll)distance(v.begin(), lower_bound((v).begin(), (v).end(), e))
#define upper_index(v, e) (ll)distance(v.begin(), upper_bound((v).begin(), (v).end(), e))
ll mpow(ll a, ll n,ll mod=MOD){ll res=1;while(n>0){if(n&1)res=res*a%mod;a=a*a%mod;n>>=1;}return res;}
template<class T1, class T2> ll bcount(T1 v, T2 a){return upper_index(v,a)-lower_index(v,a);} 
template<class T> bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
template<class T> void debug2(T v){rep(i,v.size()){rep(j,v[i].size())cout<<v[i][j]<<" ";cout<<endl;}}
template<class T> void rdv(T &v){rep(i,v.size())cin>>v[i];}
template<class T> void rdvv(T &v){rep(i,v.size()){rep(j,v[i].size())cin>>v[i][j];}}
// multimap
// mmap.emplace(key,value);
// auto ngw = list.equal_range("");
// for(auto e = ngw.first; it != ngw.second ; ++e)


int main(){
    ll N, Q; cin >> N >> Q;
    string S; cin >> S;
    vector<ll> lct;
    rep(i, N-1){
        if(S[i] == 'A' && S[i+1] == 'C') lct.push_back(i);
    }
    ll siz = lct.size();
    rep(i, Q){
        ll l, r; cin >> l >> r;
        cout << (siz - lower_index(lct, l - 1)) - (siz - upper_index(lct, r - 2)) << endl; 
    }

    return 0;
}

Measured memory_bytes: 1528
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <map>
#include <numeric>
using namespace std;

int main()
{
  long long H,W;
  long long s1,s2,s3,mi,ma,ans=100000000;

  cin>>H>>W;
  for(int i=1;i<H;i++){
    s1=W*i;
    s2=(H-i)*(W/2);
    s3=(H-i)*(W-W/2);
    mi=min(min(s1,s2),s3);
    ma=max(max(s1,s2),s3);
    ans=min(ma-mi,ans);
    s2=((H-i)/2)*W;
    s3=((H-i)-(H-i)/2)*W;
    mi=min(min(s1,s2),s3);
    ma=max(max(s1,s2),s3);
    ans=min(ma-mi,ans);
  }
  swap(H,W);

  for(int i=1;i<H;i++){
    s1=W*i;
    s2=(H-i)*(W/2);
    s3=(H-i)*(W-W/2);
    mi=min(min(s1,s2),s3);
    ma=max(max(s1,s2),s3);
    ans=min(ma-mi,ans);
    s2=((H-i)/2)*W;
    s3=((H-i)-(H-i)/2)*W;
    mi=min(min(s1,s2),s3);
    ma=max(max(s1,s2),s3);
    ans=min(ma-mi,ans);
  }

  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <cassert>

using namespace std;

const int N = 100'009;

int n;
vector<int> g[N];
int a[N];
int b[N];
bool was[N];
int q[N];
int d[N];
int deg[N];

int bfs(int from) {
  const int inf = 1'000'000'000;
  for (int i = 0; i < n; ++i) {
    d[i] = inf;
  }
  d[from] = b[from] - a[from];
  q[0] = from;
  for (int qh = 0, qt = 1; qh < qt; ++qh) {
    int x = q[qh];
    for (int y : g[x]) {
      if (!was[y] && d[y] == inf) {
        d[y] = d[x] + b[y] - a[y] - 1;
        q[qt++] = y;
      }
    }
  }
  int ver = 0;
  for (int i = 0; i < n; ++i) {
    if (d[i] < d[ver]) {
      ver = i;
    }
  }
  assert(deg[ver] == 1);
  return ver;
}

char t[N];

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    g[i].clear();
  }
  for (int i = 0; i < n - 1; ++i) {
    int x, y;
    scanf("%d %d", &x, &y);
    --x;
    --y;
    g[x].push_back(y);
    g[y].push_back(x);
    ++deg[x];
    ++deg[y];
  }
  scanf("%s", t);
  for (int i = 0; i < n; ++i) {
    a[i] = t[i] == 'W';
  }
  memset(was, false, sizeof was);
  int qt = 0;
  for (int i = 0; i < n; ++i) {
    if (deg[i] <= 1 && a[i] == 0) {
      was[i] = true;
      q[qt++] = i;
    }
  }
  for (int qh = 0; qh < qt; ++qh) {
    int x = q[qh];
    for (int y : g[x]) {
      --deg[y];
      if (deg[y] <= 1 && a[y] == 0 && !was[y]) {
        was[y] = true;
        q[qt++] = y;
      }
    }
  }
  int rem = 0;
  for (int i = 0; i < n; ++i) {
    if (!was[i]) {
      ++rem;
    }
  }
  if (rem == 0) {
    puts("0");
    return 0;
  }
  if (rem == 1) {
    puts("1");
    return 0;
  }
  int sum = 0;
  int ver = -1;
  for (int i = 0; i < n; ++i) {
    if (!was[i]) {
      if (deg[i] == 1) {
        a[i] = 0;
        b[i] = 0;
      } else {
        a[i] ^= deg[i] % 2;
        b[i] = a[i] ^ 1;
      }
      sum += a[i];
      ver = i;
    }
  }
  printf("%d\n", 2 * (rem - 1) + sum + 1 + d[bfs(bfs(ver))]);
}


Measured memory_bytes: 8312
#define _USE_MATH_DEFINES
#include <iostream>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <set>
#include <array>
#include <stdio.h>
#include <string.h>
using ll = long long;
using ull = unsigned long long;
using namespace std;
#define int long long
#define CONTAINS_VEC(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define ARY_REVERSE(v,a) (reverse((v), (v)+(a)))
#define REP(i, n) for (int (i)=0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()
#define CONTAINS_SET(m, a) (m).find((a)) != m.end()
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }

signed main()
{
	int a, b, x;
	cin >> a >> b >> x;
	YESNO(a <= x && x <= a + b);
}



Measured memory_bytes: 3104
import java.util.*;
 
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		int[] l = new int[N];
		int[] use = new int[N]; //n本目の棒を0=使わない、1=A,2=B,3=Cに使う
		for(int i=0;i<N;++i){
			l[i] = sc.nextInt();
			use[i] = 0;
		}
		use[N-1] = 1;

		int ans = Integer.MAX_VALUE;
		while(true){
			int la = 0;
			int lb = 0;
			int lc = 0;
			int as = 0;
			int bs = 0;
			int cs = 0;
			for(int i=0;i<N;++i){
				if(use[i]==1){
					la+=l[i];
					as++;
				}else if(use[i]==2){
					lb+=l[i];
					bs++;
				}else if(use[i]==3){
					lc+=l[i];
					cs++;
				}
			}
			if(as!=0&&bs!=0&&cs!=0){
				int res = Math.abs(la-A)+Math.abs(lb-B)+Math.abs(lc-C)+(as+bs+cs-3)*10;
				ans = Math.min(ans,res);
			}

			use[N-1]++;
			for(int i=N-1;i>0;--i){
				if(use[i]!=4) break;
				else{
					use[i] = 0;
					use[i-1]++;
				}
			}
			if(use[0] == 4) break;
		}

		System.out.println(ans);
		return;
	}
}

Measured memory_bytes: 23764
#include<iostream>
#include<string>
using namespace std;
string s;
int a[1000001],b[1000001],num[1000001],dp[1000001][2];
int main()
{
	cin>>s;
	int alen=s.length();
	for(int i=0;i<alen;i++) num[i]=s[i]-'0';
	dp[0][0]=num[0];
	dp[0][1]=11-num[0];
	for(int i=1;i<alen;i++)
	{
		dp[i][0]=min(dp[i-1][0]+num[i],dp[i-1][1]+num[i]);
		dp[i][1]=min(dp[i-1][0]+11-num[i],dp[i-1][1]+9-num[i]);
	}
	cout<<min(dp[alen-1][0],dp[alen-1][1])<<endl;
	return 0;
}


Measured memory_bytes: 13700
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int n , a[N] , b[N];

bool g[N][N];
bool check(long long mask) {
    memset(g , 0 , sizeof(g));
    for (int i = 0 ; i < N ; ++ i) {
        for (int k = 1 ; k <= 50 ; ++ k) {
            if (mask >> k & 1) {
                g[i][i % k] = 1;
            }
        }
        g[i][i] = 1;
    }
    for (int k = 0 ; k < N ; ++ k) {
        for (int i = 0 ; i < N ; ++ i) {
            for (int j = 0 ; j < N ; ++ j) {
                g[i][j] |= g[i][k] && g[k][j];
            }
        }
    }
    for (int i = 0 ; i < n ; ++ i) {
        if (!g[a[i]][b[i]]) {
            return 0;
        }
    }
    return 1;
}

long long dfs(int w , long long mask) {
    if (w == 0) {
        return mask;
    } else {
        if (check(mask & ~(1LL << w))) {
            return dfs(w - 1 , mask & ~(1LL << w));
        } else {
            return dfs(w - 1 , mask);
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0 ; i < n ; ++ i) {
        cin >> a[i];
    }
    for (int i = 0 ; i < n ; ++ i) {
        cin >> b[i];
    }
    if (!check((1LL << 51) - 2)) {
        cout << -1 << endl;
    } else {
        cout << dfs(50 , (1LL << 51) - 2) << endl;
    }
}


Measured memory_bytes: 256
N, upper_bit = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)
already_min = false

ans = 0
mask = 1 << 39
39.step(0, -1) do |digest|
  ones = A.count { |str| (str & mask) > 0 }
  if ones * 2 >= N
    already_min = true if upper_bit[digest] == 1
    ans += mask * ones
  else
    if already_min || (upper_bit[digest] == 1)
      ans += mask * (N - ones)
    else
      ans += mask * ones
    end
  end
  mask = mask >> 1
end
p ans


Measured memory_bytes: 8972
#  --*-coding:utf-8-*--

import heapq

INF = float('inf')

def dijkstra(graph, st):
    n  = len(graph)
    ds = [[INF]*3 for _ in range(n)]
    ds[st][0] = 0
    ds[st][1] = INF
    ds[st][2] = INF
    
    qs = [(0, st, 0)]
    heapq.heapify(qs)

    while len(qs) > 0:
        d, nodeId, mod = heapq.heappop(qs)
        
        if d > ds[nodeId][mod]:
            continue
        
        for destId in graph[nodeId]:
            d2 = d + 1
            mod2 = d2%3

            if ds[destId][mod2] > d2:
                ds[destId][mod2] = d2
                heapq.heappush(qs, (d2, destId, mod2))
                
    return (ds)


def main():
    N, M = map(int, input().split())
    
    V = [[] for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        V[u-1].append(v-1)

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

    ds = dijkstra(V, S-1)
    x = ds[T-1][0]

    print(x//3 if x != INF else -1)



if __name__ == '__main__':
    main()


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

struct qnode
{
    int v,c;
    qnode(int _v = 0, int _c = 0):v(_v),c(_c){}
    bool operator<(const qnode& b) const
    {
        return c > b.c;
    }
};

struct Edge
{
    int v,cost;
    Edge(int _v = 0, int _cost = 0):v(_v),cost(_cost){}
};
const int MAXN = 1e6+10;
const int INF = 0x3f3f3f3f;
map<pair<int, int>, int> mp;
int n,m,st;
vector<Edge> E[MAXN];
bool vis[MAXN];
int dist[MAXN];

void addedge(int u, int v, int w)
{
    E[u].push_back(Edge(v,w));
}

void Dijkstra(int n, int start)
{
    memset(vis,0,sizeof(vis));
    memset(dist,INF,sizeof(dist));
    priority_queue<qnode> que;
    dist[start] = 0;
    que.push(qnode(start,0));
    qnode tmp;
    while(!que.empty())
    {
        tmp = que.top();
        que.pop();
        int u = tmp.v;
        if(vis[u]) continue;
        vis[u] = true;
        for(int i = 0; i < E[u].size(); ++i)
        {
            int v = E[tmp.v][i].v;
            int cost = E[u][i].cost;
            if(!vis[v] && dist[v] > dist[u]+cost)
            {
                dist[v] = dist[u]+cost;
                que.push(qnode(v,dist[v]));
            }
        }
    }
}

void init()
{
    st = n;
}

int getid(int u, int c)
{
    if(mp.find(make_pair(u,c)) != mp.end())
        return mp[make_pair(u,c)];
    return mp[make_pair(u,c)] = ++st;
}

int main()
{
    int a,b,c,ta,tb;
    scanf("%d %d",&n,&m);
    init();
    for(int i = 0; i < m; ++i)
    {
        scanf("%d %d %d",&a,&b,&c);
        ta = getid(a,c);
        tb = getid(b,c);
        addedge(ta,tb,0);
        addedge(tb,ta,0);

        addedge(a,ta,1);
        addedge(ta,a,1);

        addedge(b,tb,1);
        addedge(tb,b,1);
    }
    Dijkstra(n,1);
    printf("%d\n",dist[n] == INF?-1:dist[n]/2);
    return 0;
}


Measured memory_bytes: 72828
n = int(input())

ordered_menus = [int(i) for i in input().split()]
menu_values = [int(i) for i in input().split()]
additional_happiness = [int(i) for i in input().split()]

res = 0

res += sum(menu_values)

for i in range(n-1):
    if ordered_menus[i+1] - ordered_menus[i] == 1:
        res += additional_happiness[ordered_menus[i] - 1]

print(res)

Measured memory_bytes: 3064
#include<iostream>

using namespace std;

int main(){
    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; i++) cin >> a[i];
    int mx = 0;
    int submx = 0;
    for(int i = 0; i < n; i++){
        if (submx < a[i]) {
            if (mx < a[i]) {
                submx = mx;
                mx = a[i];
            }else{
                submx = a[i];
            }
        }
    }
    for(int i = 0; i < n; i++){
        if (a[i] == mx) {
            cout << submx << endl;
        }else{
            cout << mx << endl;
        }
        
    }
    
    
}

Measured memory_bytes: 2432