akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
public class Main {
    public static void main(String [] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long L [] = new long[n];
        for(int i=0;i<n;i++)L[i] = sc.nextLong();
        int q = sc.nextInt();
        for(int i=0;i<q;i++){
            int b = sc.nextInt();
            int e = sc.nextInt();
            long k = sc.nextLong();
            int cnt = 0;
            for(int j=b;j<e;j++) if(L[j] == k) cnt++;
            System.out.println(cnt);
        }
    }
}


Measured memory_bytes: 36608
from collections import deque

[H, W] = [int(i) for i in input().split()]
S = [list(input()) for _ in range(H)]
dy, dx = [1, 0, -1, 0], [0, 1, 0, -1]

def bfs(sy, sx):
    if S[sy][sx] == '#':
        return 0
        
    reached = [[-1]*W for _ in range(H)]
    que = deque([[sy, sx]])
    reached[sy][sx] = 0
    
    while que:
        [y, x] = que.pop()
        for i in range(4):
            yy, xx = y + dy[i], x + dx[i]
            if yy < 0 or xx < 0 or yy > H-1 or xx > W-1 or S[yy][xx] == '#' or reached[yy][xx] != -1:
                continue
            else:
                reached[yy][xx] = reached[y][x] + 1
                que.appendleft([yy, xx])
                
    distance = 0
    for i in range(H):
        for j in range(W):
            distance = max(distance, reached[i][j])
            
    return distance

ans = 0
for a in range(H):
    for b in range(W):
        ans = max(ans, bfs(a, b))

print(ans)


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

using ll = long long int;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

ll a, b;

vector<ll> store;

ll ans = 0;

/////////////////////////////////////////////////////////////
ll mypow_core(ll x, int n, ll result) {
  if (n == 0) {
    return result;
  }

  if (n % 2 == 0) {
    return mypow_core(x * x, n / 2, result);
  }
  else {
    return mypow_core(x, n - 1, x * result);
  }
}

ll mypow(ll x, int n) {
  return mypow_core(x, n, 1);
}
/////////////////////////////////////////////////////////////

ll count_one(int k, ll x) {
  ll band = mypow(2, k + 1);

  ll part = (x + 1) / band;

  ll num = mypow(2, k) * part;

  ll cut = (x + 1) % band;

  if (cut == 0) {
    return num;
  }
  else {
    if (cut >= (band / 2) + 1) {
      return num + cut - ((band / 2) + 1) + 1;
    }
    else {
      return num;
    }
  }
}

int main(void) {
  // Here your code !
  scanf("%lld %lld", &a, &b);

  int size = log2(b) + 1;

  for (int i = 0; i <= size; ++i) {
    ll bottom = count_one(i, a - 1);
    ll top = count_one(i, b);

    ll num_one = top - bottom;

    if (num_one % 2 == 0) {
      store.push_back(0);
    }
    else {
      store.push_back(1);
    }
  }

  for (int i = 0; i < store.size(); ++i) {
    ans += mypow(2, i) * store[i];
  }

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

  return 0;
}


Measured memory_bytes: 512
#define _GLIBCXX_DEBUG
// header {{{
#include <bits/stdc++.h>
using namespace std;
#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y
#define ASSERT(expr...) assert((expr))
using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
using f80 = __float80;
// }}}
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
// util {{{
#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }
template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }
template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}

template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}
// }}}

// init {{{
struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;
// }}}

//--------------------------------------------------------------------

signed main() {
    int n;
    cin>>n;
    vector<int> x(n), y(n);
    REP(i,n){
        cin>> x.at(i) >> y.at(i);
    }

    double sum = 0;
    REP(i,n){
        REP(j,n){
            sum += sqrt( pow(x.at(i)-x.at(j),2) + pow(y.at(i)-y.at(j),2));
        }
    }
    double w = sum/n;
    cout<<w<<endl;

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define P(x) cout << (x) << endl
#define p(x) cout << (x)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define vv(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i));
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a); i>n; --i)
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
typedef long long ll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
int main() {
	int n; cin >> n;
	int max_t = -1e9, t;
	cin >> t;
	int min_t = t;
	rep(i, 1, n) {
		cin >> t;
		if(max_t < t - min_t) max_t = t - min_t;
		if(min_t > t) min_t = t;
	}
	P(max_t);
	return 0;
}

Measured memory_bytes: 3220
#include <bits/stdc++.h>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <map>
#include <bitset>
#include <cmath>
#include <set>

#define INF 1000000000000
#define MOD 1000000007 //10^9+7:合同式の法

using namespace std;
typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)

int main(){
    ll L ,R;
    cin >> L >> R;
    int min2019=2019,minI= 3000,minJ=3000;
    ll iset,i0,j0,tmp;

    for(ll i = L;i < R and i < L + 2019;i++){
        for(ll j = L + 1;j <= R and j <= L + 2019;j++){
            if(min2019 == 0){
                break;
            }else{
                i0 = i % 2019;
                j0 = j % 2019; 
                tmp = (i0 * j0) % 2019;             
                if(min2019 > tmp){
                    min2019 = tmp;
                }
            }
        }      
        
    }

    cout << min2019 << endl;
    
}

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

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define ALLTRUE(xs) all_of(ALL(xs),[](bool x){return x;})
#define AND(x,y,z) set_intersection((x).begin(),(x).end(),(y).begin(),(y).end(),inserter((z),(z).end()))
#define ANYTRUE(xs) any_of(ALL(xs),[](bool x){return x;})
#define CONCAT(x,y) (x).insert((x).end(),(y).begin(),(y).end())
#define DUMP(xs) for (auto x:xs) cout<<x<<' ';cout<<endl
#define DUMPP(xs) for (auto x:xs) cout<<'('<<x.first<<','<<x.second<<')';cout<<endl
#define FOR(i,a,b) for (ll i=(ll)(a);i<(ll)(b);++i)
#define OR(x,y,z) set_union((x).begin(),(x).end(),(y).begin(),(y).end(),inserter((z),(z).end()))
#define OUT(x) cout<<x<<endl
#define REP(i,n) FOR(i,0,n)

template<class T> void YES(T condition){ if(condition) OUT("YES"); else OUT("NO"); }
template<class T> void Yes(T condition){ if(condition) OUT("Yes"); else OUT("No"); }
template<class T> bool mmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<class T> bool mmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }

typedef long long ll;
typedef pair<ll, ll> P;

const int MOD=1e9+7;

int main() {
  // 方針としては、コストを0にする人数が最大になるように割り振る
  // つまりコストの昇順でそーとして、小さいものから順番に減らしていき
  // 残ったものを食べにくさの降順にぶつける
  //
  // コストの合計-Kをfoodにうまく割り振って、最大を最小にする
  // foodの食べにくさが小さい順に割り振った方がいいので降順ソート
  // そして、最小の食べにくさのところに優先的に降っていって、その合計が次の食べ物x1を超えたらそっちに割り振っていく
  ll N,K;cin>>N>>K;
  vector<ll> AS(N),FS(N);
  REP(i,N) cin>>AS[i];
  REP(i,N) cin>>FS[i];
  sort(ALL(AS),greater<ll>());
  sort(ALL(FS));

  // もし全員コスト0にできるなら
  if (accumulate(ALL(AS),0LL)<=K) {
    OUT(0);
    return 0;
  }

  ll costs = accumulate(ALL(AS),0LL)-K;

  // 入れた値以下にできるか
  auto checker = [&](ll limit) {
    // メンバーが全員いけるか
    ll tmp = 0;
    REP(i,N) {
      if (FS[i]*AS[i]<=limit) tmp+=AS[i];
      else tmp += limit/FS[i];
    }
    return costs<=tmp;
  };

  ll left=0,right=FS.back()*AS.front();
  while (left<right) {
    ll mid = (left+right)/2;
    if (checker(mid)) right = mid;
    else left = mid+1;
  }
  OUT(left);

  return 0;
}

Measured memory_bytes: 3456
import std.stdio, std.string, std.conv;
import std.array, std.algorithm, std.range;

void main()
{
    foreach(s;stdin.byLine())
    {
        auto c = s.split().map!(to!real).array();
        auto r = 20-c[0]-c[1];
        writeln(r-c.count!(i=>i<=r)()>3?"YES":"NO");
    }
}

Measured memory_bytes: 1088
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100100;
vector<pair<int,int> > to[maxn];
int deg[maxn], ans[maxn];
void dfs(int r, int p, int c){
	set<int> now;
	now.insert(c);
	int cur = 1;
	for(auto e : to[r]){
		if(e.first == p) continue;
		while(now.count(cur)) cur++;
		ans[e.second] = cur;
		dfs(e.first, r, cur);
		now.insert(cur);
	}
}
int main(){
	int n; cin >> n;
	for(int i = 0; i < n - 1; i++){
		int u, v; cin >> u >> v; u--; v--;
		to[u].push_back({v, i});
		to[v].push_back({u, i});
		deg[u]++;
		deg[v]++;
	}
	int r = max_element(deg, deg + n) - deg;
	dfs(r, -1, -1);
	cout << deg[r] << "\n";
	for(int i = 0; i < n - 1; i++) cout << ans[i] << "\n";
	return 0;
}


Measured memory_bytes: 14976
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main(){
    int n;
    cin >> n;
    bool ok = true;
    rep(i, n) {
        int a;
        cin >> a;
        if ( a&1 ) continue;
        if ( a % 3 != 0 && a % 5 != 0 ) ok = false;
    }
    cout << ((ok) ? "APPROVED" : "DENIED") << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

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

	ll n;
	cin >> n;
	vector<string> s(n);
	set<string> st;
	REP(i, n){
		cin >> s[i];
		if(st.find(s[i]) != st.end()){
			cout << "No" << endl;
			return 0;
		}
		st.insert(s[i]);
		if(i && s[i][0] != s[i - 1][s[i - 1].size() - 1]){
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
sx,sy,tx,ty = [int(i) for i in input().split()]
ans = ""
for i in range(ty-sy):
    ans += "U"
for i in range(tx-sx):
    ans += "R"
for i in range(ty-sy):
    ans += "D"
for i in range(tx-sx):
    ans += "L"
ans += "L"
for i in range(ty-sy+1):
    ans += "U"
for i in range(tx-sx+1):
    ans += "R"
ans += "D"
ans += "R"
for i in range(ty-sy+1):
    ans += "D"
for i in range(tx-sx+1):
    ans += "L"
ans += "U"

print(ans)

Measured memory_bytes: 3064
#include<cstdio>
#include<iostream>
using namespace std;
int main(){
	int a,b,c,x,y,ans;
	scanf("%d%d%d%d%d",&a,&b,&c,&x,&y);
	if(x<=y){
		if(a+b>=2*c) ans=2*c*x+min(b,2*c)*(y-x);
		else ans=a*x+b*y;
	}
	else if(x>y){
		if(a+b>=2*c) ans=2*c*y+min(a,2*c)*(x-y);
		else ans=a*x+b*y;
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/adaptor/indexed.hpp>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x) begin(x),end(x)

using namespace std;
using namespace boost::adaptors;
using namespace std::string_literals;
using ll = int64_t;
using vecint = vector<int>;
using vecll = vector<ll>;
using boost::irange;

int main() {
  ll l;
  cin>>l;
  vecll a(l);
  for(auto&& e:a)cin>>e;
  constexpr ll INF = 1e15;
  vector<vecll> dp(5, vecll(l+1, INF));
  dp[0][0] = 0;
  REP(i,l) {
    dp[0][i+1] = dp[0][i] + a[i];
    dp[1][i+1] = min(dp[1][i], dp[0][i]) + a[i] % 2 + (a[i] == 0 ? 2 : 0);
    dp[2][i+1] = min({dp[2][i], dp[1][i], dp[0][i]}) + (a[i] + 1) % 2;
    dp[3][i+1] = min({dp[3][i], dp[2][i], dp[1][i], dp[0][i]}) + a[i] % 2 + (a[i] == 0 ? 2 : 0);
    dp[4][i+1] = min({dp[4][i], dp[3][i], dp[2][i], dp[1][i], dp[0][i]}) + a[i];
  }
  ll ans = INF;
  REP(i,5) ans = min(ans, dp[i][l]);
  cout<<ans<<endl;
  return 0;
}


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

vector<double> x(10), y(10);

double dist(int i, int j) {
    double dx = x[i] - x[j];
    double dy = y[i] - y[j];
    return pow(dx * dx + dy * dy, 0.5);
}

int main() {
  double N, M;
  cin >> N;
  double ans = 0;
  rep(i, N) cin >> x[i] >> y[i];
  for(int i = 0; i < N - 1; i++) {
    for(int j = i + 1; j < N; j++) ans += dist(i, j) * 2 / N;
  }
  cout << fixed << setprecision(10) << ans << endl;
  return 0;
}


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

  int cnth[1500001],cntw[1500001];

int main(){
  while(1){
    
    memset(cnth,0,sizeof(cnth)),memset(cntw,0,sizeof(cntw));
  int n,m;
  cin>>n>>m;
  if(n+m==0) break;
  int h[1500],w[1500];
  for(int i=0;i<n;i++)cin>>h[i];
  for(int i=0;i<m;i++)cin>>w[i];
  
  
  for(int i=0;i<n;i++){
    int ph=h[i];
    cnth[ph]++;
    for(int j=i+1;j<n;j++)ph+=h[j],cnth[ph]++;
  }
  
  for(int i=0;i<m;i++){
    int pw=w[i];
    cntw[pw]++;
    for(int j=i+1;j<m;j++)pw+=w[j],cntw[pw]++;
    }
  
  int ans=0;
  for(int i=1;i<=1500000;i++)if(cnth[i]>0 && cntw[i]>0)ans+=(cnth[i]*cntw[i]);
  
  cout<<ans<<endl;
  }
  return 0;
}

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

#define PI 3.1415926535897932
#define MOD 1000000007
#define INF 1e9

#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define FOR(i, start, end) for(int i = (start); i < (end); i++)
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;

void solve()
{
    ll N, K; cin >> N >> K;
    vector<pii> array(N); REP(i, N) cin >> array[i].first >> array[i].second;
    sort(ALL(array));
    ll sum = 0;
    REP(i, N)
    {
        sum += array[i].second;
        if(sum >= K)
        {
            cout << array[i].first << endl;
            return;
        }
    }
}

int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();

    return 0;
}

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

#define ll long long
#define mod 1000000007
#define mod2 998244353
#define pii pair<ll,ll>
#define pb push_back

#define debug(a) { cout << #a << " = " << a << endl;}

void sep() {
    cout << "-------------BLOCK-----------------\n";
}

template<typename T>
void debugv(vector<T> arr) {
    for (auto t: arr)
        cout << t << " ";
    cout << "\n";
}

template<typename T>
void debugarr(T arr, int n) {
    for (int i=0;i<n;i++) cout << arr[i] << " ";
    cout << "\n";
}

ll __min(ll a, ll b) {
    return a < b ? a : b;
}

ll __max(ll a, ll b) {
    return a > b ? a : b;
}

const int maxn = 1e5+1;
ll arr[maxn], n, m, t, k, q;
unordered_map<ll,ll> u;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int arr[26]={0};
    string s;
    cin>>s;
    for (char c: s) arr[c-'a']++;
    for (int i=0;i<26;i++) {
        if (arr[i] == 0) {
            char c = 'a' + i;
            cout << c << endl;
            exit(0);
        }
    }
    cout << "None\n";
}


Measured memory_bytes: 3852
n,dum=gets.chomp.split(' ').map{|n| n}
a,b,c,d=n.split("").map{|i| i.to_i}

if(a+b+c+d==7)
	puts "#{a}+#{b}+#{c}+#{d}=7"
elsif(a+b+c-d==7)
	puts "#{a}+#{b}+#{c}-#{d}=7"
elsif(a+b-c+d==7)
	puts "#{a}+#{b}-#{c}+#{d}=7"
elsif(a+b-c-d==7)
	puts "#{a}+#{b}-#{c}-#{d}=7"
elsif(a-b+c+d==7)
	puts "#{a}-#{b}+#{c}+#{d}=7"
elsif(a-b+c-d==7)
	puts "#{a}-#{b}+#{c}-#{d}=7"
elsif(a-b-c+d==7)
	puts "#{a}-#{b}-#{c}+#{d}=7"
elsif(a-b-c-d==7)
	puts "#{a}-#{b}-#{c}-#{d}=7"
end


Measured memory_bytes: 1788
// In the name of God

#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>
#include <complex>

using namespace std;

#define rep(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
//#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline bool smin(T &a, const T &b)   { return a > b ? a = b : a;    }
template<typename T> inline bool smax(T &a, const T &b)   { return a < b ? a = b : a;    }

typedef long long LL;

const int N = (int) 1e5 + 5, mod = (int) 0;
int n, done;
map<int, int> mp[N];
int ask(int x, int y) {
	if (mp[x][y]) return mp[x][y] - 1;
	++done;
	if (done >= 2 * n) {
		assert(0);
	}
	cout << "? " << x << ' ' << y << endl;
	fflush(stdout);
	char res;
	cin >> res;
	mp[x][y] = (res == 'Y') + 1;
	return res == 'Y';
}
char s[N];
int main() {
	int a, b;
	cin >> a >> b;
	if (a <= b) {
		cout << "Impossible" << endl;
		fflush(stdout);
		return 0;
	}
	vector<int> all;
	n = a + b;
	for (int j = 0; j < n; ++j) {
		if (!all.size()) {
			all.push_back(j);
		} else {
			int x = ask(all.back(), j);
			if (!x) {
				all.pop_back();
			} else {
				all.push_back(j);
			}
		}
	}
	int good = all.back();
	/*
	while (all.size() > 1) {
		vector<int> nx;
		if (all.size() == 3) {
			int x = ask(all[0], all[2]);
			int y = ask(all[1], all[2]);
			if (x + y >= 1) {
				nx.push_back(all[2]);
			} else {
				nx.push_back(all[0]);
			}
		} else {
			if ((all.size() & 1) && ((all.size() / 2) & 1)) {
				nx.push_back(all.back()); all.pop_back();
				nx.push_back(all.back()); all.pop_back();
			}
			for (int j = 0; j < (int) all.size(); j += 2) {
				int x = ask(all[j], all[j + 1]);
				if (x) nx.push_back(all[j + 1]);
			}
			if (all.size() & 1)
				nx.push_back(all.back());
		}
		all = nx;
	}
	int good = all[0];
	*/
	s[good] = '1';
	for (int j = 0; j < n; ++j)
		if (good != j) {
			s[j] = (ask(good, j) ? '1' : '0');
		}
	cout << "! ";
	string res;
	for (int j = 0; j < n; ++j) res += s[j];
	cout << res << endl;
	return 0;

}



Measured memory_bytes: 5844
#include <bits/stdc++.h>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
#define endl "\n"
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
const ll INF = 2e+9 + 10;
typedef pair<ll, ll> P;

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

  int N,K; cin >> N >> K;
  vec l(N); rep(i,N) cin >> l[i];

  sort(ALL(l), greater<int>());
  int res = 0;
  rep(i,K)res+=l[i];

  cout <<res << endl;
  return 0;
}


Measured memory_bytes: 256
a = int(input())
b = []
for i in range(a):
    c, d = map(int, input().split())
    b.append([d, c])
b.sort()
c = 0
for i in range(a):
    c += b[i][1]
    if c > b[i][0]:
        print("No")
        exit()
print("Yes")


Measured memory_bytes: 35616
n, m = map(int, input().split())
a = ['']*n
b = ['']*m
for i in range(n):
  a[i] = str(input())
for i in range(m):
  b[i] = str(input())
for i in range(n-m+2):
  c = a[i:i+m]
  for j in range(n-m+2):
    d = [e[j:j+m] for e in c]
    if b == d:
      print('Yes')
      exit()
else:
  print('No')

Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	for (int R; cin >> R&&R;) {
		static int L[2][510][510];
		vector<int> W(2), H(2), X(2), Y(2); rep(i, 0, 2) {
			cin >> W[i] >> H[i] >> X[i] >> Y[i]; X[i]--, Y[i]--;
			rep(y, 0, H[i])rep(x, 0, W[i]) {
				cin >> L[i][y][x];
			}
		}
		using T = tuple<int, int, int>;
		vector<vector<int>> level(2, vector<int>(R + 1, INF));
		rep(k, 0, 2) {
			static bool flag[510][510];
			memset(flag, 0, sizeof(flag));
			priority_queue<T, vector<T>, greater<T>> pq;
			pq.emplace(L[k][Y[k]][X[k]], Y[k], X[k]);
			flag[Y[k]][X[k]] = true;
			auto inrange = [&](int i, int j) { return i >= 0 && i < H[k] && j >= 0 && j < W[k]; };
			int c = 0;
			int nl = 0;
			while (pq.size()) {
				int l, ci, cj; tie(l, ci, cj) = pq.top(); pq.pop();
				static const int di[] = { 1,0,-1,0 };
				static const int dj[] = { 0,1,0,-1 };
				c++;
				chmax(nl, l);
				level[k][c] = nl;
				if (c == R)break;
				rep(d, 0, 4) {
					int ni = ci + di[d], nj = cj + dj[d];
					if (!inrange(ni, nj))continue;
					if (flag[ni][nj])continue;
					flag[ni][nj] = true;
					pq.emplace(L[k][ni][nj], ni, nj);
				}
			}
		}
		dump(level);
		int ans = INF;
		rep(r, 0, R + 1) {
			chmin(ans, level[0][r] + level[1][R - r]);
			dump(level[0][r], level[1][R - r]);
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 6612
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream> 
#include<unordered_map>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;
typedef vector<int> vi;
typedef vector<ll> vl;

const int inf = numeric_limits<int>::max() >> 2;
const ll linf = numeric_limits<ll>::max() >> 2;
const ull ulinf = numeric_limits<ull>::max() >> 2;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define umap(i,j) unordered_map<i,j>
#define P(p) cout<<(p)<<endl
#define PS(p) cout<<(p)<< " "
#define IN cin >> 
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i = (m-1); i >= (int)(n); i--)
#define inrep(n,a) for(int i = 0; i < (int)(n); i++)cin >> a[i];
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v,c) sort(v.begin(), v.end(), greater<c>());
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - a) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - a) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}

//ll ncr[100][100];
//ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

//ll npr[100][100]={};
//ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

//ll nHr(int n,int r){ret nCr(n+r-1,r);}

///////////////////////////////////////////////////////////////////////////


int main(){
    int n;
    cin >> n;
    int a[n];
    inrep(n,a);
    sort(a,a+n);
    int ans = 0;
    rep(i,0,n)ans += a[i];
    ans -= a[n-1]/2;
    P(ans);
    
	return  0;
}

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

#define all(x) x.begin(),x.end()
#define fi first
#define sd second
#define lson (nd<<1)
#define rson (nd+nd+1)
#define PB push_back
#define mid (l+r>>1)
#define MP make_pair
#define SZ(x) (int)x.size()

using namespace std;

typedef long long LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

const int MOD = 1e9+7;


int main(){
    LL n, k;
    scanf("%lld%lld", &n, &k);
    LL ans=0;
    for(LL i=k;i<=n+1;++i)ans=(ans+i*(n-i+1)+1)%MOD;
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 3696
#include <cstdio>
#include <cstdlib>

typedef long long ll;

ll d[111111], prefix[111111];

int main(void)
{
	ll n, m, i, a, start = 1, ans = 0;

	scanf("%lld %lld" ,&n, &m);
	for (i = 1; i < n; i++)
	{
		scanf("%lld" ,&d[i]);
		prefix[i] = prefix[i - 1] + d[i];
	}
	while (m--)
	{
		scanf("%lld" ,&a);
		ans += abs(prefix[start + a - 1] - prefix[start - 1]);
		start += a;
	}

	printf("%lld\n" ,ans % 100000);
	return 0;
}


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



int main(){
    int K,N;
    cin>>K>>N;
    vector<int> data(N);
    for(int i=0;i<N;i++)cin>>data[i];
    
    int saidai=0;

    for(int i=0;i<N-1;i++){
       int x=data[i+1]-data[i];
       saidai=max(saidai,x);
    }

    int saigo=K-data[N-1]+data[0];

    saidai=max(saigo,saidai);

    int kyori=K-saidai;

    cout<<kyori<<endl;
 
}




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

int main(){
  long long n,m;
  cin>>n>>m;
  vector<long long> a(m),b(m);
    for(long long i = 0; i < m; i++){
        cin >> a[i] >> b[i];
    }
  sort(a.begin(),a.end());
  sort(b.begin(),b.end());
  if(b[0]-a[m-1]+1>0)
  cout<<b[0]-a[m-1]+1<<endl;
  else cout<<"0"<<endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
long long pos[100005];
pair<pair<int,int>,int> query[200005];
vector<pair<int,int> > g[100005];
int n,m;
bool ishead[100005];
void dfs(int i) {
	for(int j=0;j<(int)g[i].size();j++) {
		int to=g[i][j].first,len=g[i][j].second;
		if (pos[to]) {
			if (pos[to]!=pos[i]+len) {
				puts("No");
				exit(0);
			}
		} else {
			pos[to]=pos[i]+len;
			dfs(to);
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) ishead[i]=1;
	for(int i=1;i<=m;i++) {
		int l,r,d;
		cin>>l>>r>>d;
		query[i]={{l,r},d};
		g[l].push_back({r,d});
		ishead[r]=0;
	}
	for(int i=1;i<=n;i++) {
		if (ishead[i]) {
			dfs(i);
		}
	}
	for(int i=1;i<=m;i++) {
		int l=query[i].first.first;
		int r=query[i].first.second;
		if (pos[r]-pos[l]!=query[i].second) {
			puts("No");
			return 0;
		}
	}
	puts("Yes");
	return 0;
}

Measured memory_bytes: 12928
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define ll long long

int l,r,d;

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

  
  
  
  
  printf("%d\n",r/d-(l-1)/d);
  
  return 0;
}


Measured memory_bytes: 1712
import sys
from sys import stdin
sys.setrecursionlimit(10**7)
dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)
H, W = [int(_) for _ in stdin.readline().rstrip().split()]
field = [list(stdin.readline().rstrip()) for _ in range(H)]
seen = [[False for i in range(400)] for j in range(400)]
num_b, num_w = 0, 0
ans = 0

def dfs(h, w):
    seen[h][w] = True
    if field[h][w] == '#':
        global num_b
        num_b += 1
    else:
        global num_w
        num_w += 1

    for direction in range(4):
        nh = h + dx[direction]
        nw = w + dy[direction]

        if nh < 0 or nh >= H or nw < 0 or nw >= W:
            continue
        if field[nh][nw] == field[h][w]:
            continue
        if seen[nh][nw]:
            continue

        dfs(nh, nw)

for i in range(H):
    for j in range(W):
        if field[i][j] == '.':
            continue
        if seen[i][j]:
            continue
        num_b, num_w = 0, 0
        dfs(i, j)
        ans += num_b * num_w 

print(ans)

Measured memory_bytes: 149448
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}

int main() {
    int h, w;
    cin >> h >> w;
    int n;
    cin >> n;
    vi a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vi colors;
    int color = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < a[i]; ++j) {
            colors.push_back(color);
        }
        color++;
    }
    vvi ret(h, vi(w));
    int k = 0;
    for (int i = 0; i < h; ++i) {
        if (i % 2 == 0) {
            for (int j = 0; j < w; ++j) {
                ret[i][j] = colors[k];
                k++;
            }
        } else {
            for (int j = w - 1; j >= 0; --j) {
                ret[i][j] = colors[k];
                k++;
            }
        }
    }
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cout << ret[i][j];
            if (j == w - 1)
                cout << endl;
            else
                cout << " ";
        }
    }
    return 0;
}

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

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

	int N;
	cin >> N;

	vector<tuple<int, int, int>> a( N+1 );
	for( int i = 1; i <= N; ++i ) {
		cin >> get<0>( a[i] );
		cin >> get<1>( a[i] );
		cin >> get<2>( a[i] );
	}

	bool result = true;
	for( int i = 1; i <= N; ++i ) {
		int t = get<0>( a[i] ) - get<0>( a[i-1] );
		int x = abs( get<1>( a[i] ) - get<1>( a[i-1] ) );
		int y = abs( get<2>( a[i] ) - get<2>( a[i-1] ) );

		if( t < x+y || (t & 1) != (x+y & 1) ) {
			result = false;
			break;
		}
	}

	cout << (result ? "Yes" : "No") << endl;

	return 0;
}


Measured memory_bytes: 1408
/*--------------------------"SABUJ-JANA"------"JADAVPUR UNIVERSITY"--------*/
/*-------------------------------@greenindia-----------------------------------*/
//
//		  _____       _           _        _
//		 / ____|     | |         (_)      | |
//		| (___   __ _| |__  _   _ _       | | __ _ _ __   __ _
//		 \___ \ / _` | '_ \| | | | |  _   | |/ _` | '_ \ / _` |
//		 ____) | (_| | |_) | |_| | | | |__| | (_| | | | | (_| |
//		|_____/ \__,_|_.__/ \__,_| |  \____/ \__,_|_| |_|\__,_|
//		                        _/ |
//		                       |__/
/*---------------------- Magic. Do not touch.-----------------------------*/
/*------------------------------God is Great/\---------------------------------*/
#include <bits/stdc++.h>
using namespace std;
#define crap ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
//cout<<fixed<<showpoint<<setprecision(12)<<ans<<endl;
#define int long long int
#define double long double
#define PI acos(-1)
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
#define endl "\n"

void print1d(const vector<int>& vec) {for (auto val : vec) {cout << val << " ";} cout << endl;}

void print2d(const vector<vector<int>>& vec) {for (auto row : vec) {for (auto val : row) {cout << val << " ";} cout << endl;}}

void solve(vector<int>& arr, int n) {
	int cnt = 0;
	for (int i = 1; i < n ; i++) {
		if (arr[i] == i) {
			swap(arr[i], arr[i + 1]);
			cnt++;
		}
	}

	if (arr[n] == n) {
		swap(arr[n - 1], arr[n]);
		cnt++;
	}

	cout << cnt << endl;
}

signed main() {
	crap;

	int n;
	cin >> n;

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

	solve(arr, n);


	return 0;
}

Measured memory_bytes: 3988
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {
    static final int MOD = 1000000007;
    static final int INF = 1 << 30;
    static final int ALF = 26;

    Main() {
        Scanner sc = new Scanner(System.in);
        long ans = 0;
        long A = sc.nextLong();
        long B = sc.nextLong();
        long N = sc.nextLong();
        double da = A;
        double db = B;
        if(B-1<N){
            ans = (long)Math.floor(da*(B-1)/db) - A * (long)Math.floor((B-1)/db);
        }else{
            ans = (long)Math.floor(da*N/db) - A * (long)Math.floor(N/db);
        }
        System.out.println(ans);
    }

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


Measured memory_bytes: 35632
from operator import itemgetter
import sys


def read():
    return sys.stdin.readline().rstrip()


def add(arr, i, x):
    while i < len(arr):
        arr[i] += x
        i += i & -i


def range_sum(arr, a, b):
    s = 0
    i = b
    while i > 0:
        s += arr[i]
        i -= i & -i
    i = a - 1
    while i > 0:
        s -= arr[i]
        i -= i & -i
    return s


def main():
    n, q = map(int, read().split())
    c = [int(i) - 1 for i in read().split()]
    queries = [(0, 0, 0) for _ in range(q)]
    for i in range(q):
        l, r = map(int, read().split())
        queries[i] = (i, l, r)
    queries = iter(sorted(queries, key=itemgetter(2)))
    last = [0] * n
    bit = [0] * (n + 1)
    ans = [-1] * q
    k, l, r = next(queries)
    for i in range(n):
        ci = c[i]
        li = last[ci]
        if li > 0:
            add(bit, li, -1)
        last[ci] = i + 1
        add(bit, i + 1, 1)
        while i + 1 == r:
            ans[k] = range_sum(bit, l, r)
            try:
                k, l, r = next(queries)
            except StopIteration:
                break
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()


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

namespace atcoder.abc169.c
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] paramArray = getStringParams();

            string[] digit = paramArray[1].Split('.');

            long A = long.Parse(paramArray[0]);
            long B = long.Parse(digit[0]) * 100 + long.Parse(digit[1]);

            Console.WriteLine((A * B) / 100);
        }

        //↓↓↓ shared function ↓↓↓
        static int getIntParam()
        {
            return int.Parse(Console.ReadLine());
        }
        static int[] getIntParams()
        {
            return Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
        }
        static long getLongParam()
        {
            return long.Parse(Console.ReadLine());
        }
        static long[] getLongParams()
        {
            return Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();
        }
        static string getStringParam()
        {
            return Console.ReadLine();
        }
        static string[] getStringParams()
        {
            return Console.ReadLine().Split(' ');
        }
        static decimal getDecimalParam()
        {
            return decimal.Parse(Console.ReadLine());
        }
        static decimal[] getDecimalParams()
        {
            return Console.ReadLine().Split(' ').Select(i => decimal.Parse(i)).ToArray();
        }

    }
}


Measured memory_bytes: 27164
#
# abc165 c
#
from itertools import combinations_with_replacement as cwr
import sys
from io import StringIO
import unittest
sys.setrecursionlimit(100000)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 4 3
1 3 3 100
1 2 2 10
2 3 2 10"""
        output = """110"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4 6 10
2 4 1 86568
1 4 0 90629
2 3 0 90310
3 4 1 29211
3 4 3 78537
3 4 2 8580
1 2 1 96263
1 4 2 2156
1 2 0 94325
1 4 3 94328"""
        output = """357500"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """10 10 1
1 10 9 1"""
        output = """1"""
        self.assertIO(input, output)


def resolve():
    global N, M
    N, M, Q = map(int, input().split())
    ABCD = [list(map(int, input().split())) for _ in range(Q)]

    T = []
    func([1], T)

    ans = 0
    for t in cwr(range(1, M+1), N):
        score = 0
        for abcd in ABCD:
            a, b, c, d = abcd
            if t[b-1] - t[a-1] == c:
                score += d
        ans = max(ans, score)
    print(ans)


def func(L, T):
    if len(L) == N:
        T.append(L)
        return

    for i in range(L[-1], M+1):
        NL = L + [i]
        func(NL, T)


if __name__ == "__main__":
    # unittest.main()
    resolve()


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

#define FOR(i, a, b) for(int(i)=(a);(i)<(b);(i)++)
#define REP(i, n) FOR((i), 0, (n))

#define RFOR(i, b, a) for(int(i)=(b); (i)>=(a); (i)--)
#define RREP(i, n) FOR((i), (n), 0)

#define pb push_back
#define mp make_pair 

using namespace std;

const int INF=INT_MAX/4;
const int MOD=1000000007;
const double EPS=1e-14;

const bool debug_flag=true;

void debug(string str){
	if(debug_flag){
		cout<<str<<endl;
	}
}

void debugs(string str){
	if(debug_flag){
		cout<<str;
	}
}

int main(int argc, char* argv[]){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout.precision(10);
	
	int A, B, C, ans;
	long K;
	cin>>A>>B>>C>>K;

	if(K&1){
		ans=B-A;
	}else{
		ans=A-B;
	}
	
	cout<<ans<<endl;

	return 0;
}



Measured memory_bytes: 256
import java.time.LocalDate;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String S = sc.next();

        int Y = Integer.valueOf(S.substring(0, 4));
        int M = Integer.valueOf(S.substring(5, 7));
        int D = Integer.valueOf(S.substring(8, 10));

        LocalDate P = LocalDate.of(Y, M, D);
        LocalDate mileStone = LocalDate.of(2019, 4, 30);

        if (P.compareTo(mileStone) <= 0)
            System.out.println("Heisei");
        else
            System.out.println("TBD");
    }
}





Measured memory_bytes: 21844
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
using ll = long long;

ll MOD = 1000000007;

vector<ll> mfact(1,1);


ll extGCD(ll a, ll b, ll &x, ll &y){
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    ll g = extGCD(b, a%b, y, x);
    y -= a/b * x;
    return g;
}

ll minv(ll a){
    ll x;ll y;
    extGCD(a, MOD, x, y);
    if(x<0){
        x+= ((-x)/MOD+1)*MOD;
        x %= MOD;
    }
    return x;
}

ll mpow(ll a,ll b){
    ll res = 1;
    while(b > 1){
        if(b%2==1)res=(res*a)%MOD;
        b/=2;
        a = (a*a)%MOD;
    }
    return res;
}

ll mfactorial(ll a){
    if(mfact.size()-1 >= a)return mfact[a];
    for(ll i = mfact.size();i<=a;i++){
        mfact.push_back((i * mfact[i-1])%MOD);
    }
    return mfact[a];
}

ll mcomb(ll n, ll r){
    return (((mfactorial(n) * minv(mfactorial(r)))%MOD) * minv(mfactorial(n-r)))%MOD;
}

void factorize(map<ll,ll>& fac, ll a){
    for(ll i = 2;i < ll(sqrt(a)+1);i++){
        while(a % i == 0){
            a /= i;
            fac[i]++;
        }
    }
    if(a > 1)fac[a]++;
}


int main(){
    ll N,M;
    cin>>N>>M;
    map<ll,ll> fac;
    factorize(fac,M);
    ll res = 1;
    for(auto& x:fac){
        res = (res * mcomb(x.second+N-1,N-1))%MOD;
    }
    cout<<res<<endl;
}

Measured memory_bytes: 1400
#include<iostream>

using namespace std;

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

ll n, m;

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

    if(n>=m/2){
        cout << m/2 << endl;
    } else {
        cout << n+(m-2*n)/4 << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(ll i=(a); i<(b); i++)
ll n,m;
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n>>m;
    cout<<n*(n-1)/2+m*(m-1)/2<<"\n";
}

Measured memory_bytes: 256
import string

s = input()

ans = True
if s[0] != 'A':
    ans = False
elif s[2:-1].count('C') != 1:
    ans = False
else:
    lowers = string.ascii_lowercase
    pos_c = s.find('C')
    for i in range(1, len(s)):
        if i != pos_c:
            if s[i] not in lowers:
                ans = False
                break

if ans:
    print('AC')
else:
    print('WA')

Measured memory_bytes: 3772
import heapq

def main2(l, n):
    ans = 0
    lis = []
    heapq.heapify(lis)
    for i in range(1, n):
        for j in l[i]:
            heapq.heappush(lis, j)
        while len(lis) > i:
            ans += heapq.heappop(lis)
    return ans

def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    t = int(input())

    answer = []
    for _ in range(t):

        n = int(input())
        ans = 0
        l = [[] for _ in range(n+1)]
        r = [[] for _ in range(n+1)]
        for _ in range(n):
            i, j, k = map(int, input().split())
            if j > k:
                ans += j
                l[i].append(j-k)
            elif j < k:
                if i == n:
                    ans += j
                else:
                    ans += k
                    r[n-i].append(k-j)
            else:
                ans += j

        ans -= main2(l, n) + main2(r, n)
        answer.append(ans)

    for i in answer:
        print(i)

main()

Measured memory_bytes: 47352
import math
import sys
import bisect

N = int(input())
V = [int(x) for x in input().split()]

V0 = V[0::2]
V1 = V[1::2]

def cntDict(L):
    d = dict()
    for l in L:
        d[l] = d.get(l, 0) + 1
    return d

INF = 999
def max1_2(d):
    k1 = -INF
    v1 = -INF
    k2 = -INF
    v2 = -INF
    for k in d.keys():
        v = d[k]
        if v1 < v:
            k2 = k1
            v2 = v1
            k1 = k
            v1 = v
        elif v2 < v:
            v2 = v
            k2 = k
    # return k1,v1,k2,v2
    return k1,k2

d0 = cntDict(V0)
d1 = cntDict(V1)

C0 = max1_2(d0)
C1 = max1_2(d1)

INF = 10**10

# p1
if C0[0] == C1[0]:
    p1 = INF
else:
    p1 = 0
    for v in V0:
        if v != C0[0]:
            p1+=1
    for v in V1:
        if v != C1[0]:
            p1+= 1


# //p2
if C0[0] == C1[1]:
    p2 = INF
else:
    p2 = 0
    for v in V0:
        if v != C0[0]:
            p2+=1
    for v in V1:
        if v != C1[1]:
            p2+= 1

# //p3
if C0[1] == C1[0]:
    p3 = INF
else:
    p3 = 0
    for v in V0:
        if v != C0[1]:
            p3+=1
    for v in V1:
        if v != C1[0]:
            p3+= 1

# //p4
if C0[1] == C1[1]:
    p4 = INF
else:
    p4 = 0
    for v in V0:
        if v != C0[1]:
            p4+=1
    for v in V1:
        if v != C1[1]:
            p4+= 1

ret = min(p1,p2,p3,p4)

print(ret)


pass



Measured memory_bytes: 18784
#include <iostream>
#include <vector>
#include <string>
#include <random>
#include <algorithm>
#include <iomanip>
using namespace std;

#define FOR(i,a,b) for(int i = a; i < b; ++i)
#define REP(i,n)   for(int i = 0; i < n; ++i)
typedef long long ll;
typedef unsigned long long ull;

ull powmod(ull a, ull b, ull mod) {ull res = 1; for(; b; b >>= 1){if (b & 1) {res = res * a % mod;} a = a * a % mod;} return res;}

int main(){
  ull a, b;

  ull d, r;
  double f;

  cin >> a >> b;

  d = a / b;
  r = a % b;

  f = (double)a / (double)b;

  cout << d << " " << r << " " << fixed << setprecision(6) << f << "\n";
}



Measured memory_bytes: 3296
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int a,v;
		int maxPtr=0;
		int max=-1;
		for(int i=0;i<n;i++){
			a=sc.nextInt();
			v=sc.nextInt();
			if(v>max){
				max=v;
				maxPtr=a;
			}else if(max==v&&a<maxPtr){
				max=v;
				maxPtr=a;
			}
		}
		System.out.println(maxPtr+" "+max);
	}
}

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

#ifdef LOCAL
#include "../../dump.hpp"
#else
#define dump(...)
#endif

#define rep(i,n) for(int i=0,i##_cond=(n);i<i##_cond;i++)
#define FOR(i,a,b) for(int i=(a),i##_cond=(b);i<i##_cond;i++)
#define ROF(i,a,b) for(int i=(a)-1,i##_cond=(b);i>=i##_cond;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend() //sortで大きい順
#define UNIQUE(v) v.erase(unique(all(v)),v.end())
#define SUM(a) accumulate(all(a),0)
#define sz(x) ((int)(x).size())
#define pb push_back
#define fst first
#define snd second
#define mp make_pair

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<ll,ll> pii;

#define int ll

const int inf = 1ll<<62;
const int mod = 1e9+7;

main()
{
  string x; cin >> x;

  vi a(sz(x));
  if(x[0] == 'S') a[0] = 1;
  rep(i, sz(a) - 1){
    if(x[i + 1] == 'S') a[i + 1] = a[i] + 1;
    else a[i + 1] = max(0ll, a[i] - 1);
  }

  int c = 0;
  rep(i, sz(a) - 1) if(a[i + 1] < a[i]) c++;

  cout << sz(x) - 2 * c << endl;
}

Measured memory_bytes: 2180
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _20190308_06 {
    class Program {
        static void Main(string[] args) {
            var line0 = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var n = line0[0];
            var m = line0[1];
            var line1 = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var list = new List<int>();
            for (int j = 0; j < line1[0]; j++) {
                list.Add(line1[j + 1]);
            }
            for (int i = 1; i < n; i++) {
                var line = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).Skip(1).ToArray();
                list = list.Where(x => line.Any(d => d == x)).ToList();
            }
            Console.WriteLine(list.Count);
        }
    }
}


Measured memory_bytes: 13396