akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <complex>
#include <deque>
#include <valarray>
#include <unordered_map>
#include <unordered_set>
#include <array>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <chrono>
#include <random>
#include <numeric>
using namespace std;
using ll = long long;
using ld = long double;
using str = string;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vs> vvs;
typedef vector<vc> vvc;
typedef vector<vb> vvb;
using P = pair<ll,ll>;
#define REP(i, n) for (ll i = 0; i < (int)(n); i++)
#define RREP(i, n) for (ll i = (int)(n)-1; i > -1 ; i--)
#define IN(T, x) T x;cin >> x;
#define AIN(T, a, n) vector<T> a(n);REP(i, n){cin >> a[i];}
#define A2IN(T1, a, T2, b, n) vector<T1> a(n);vector<T2> b(n);REP(i, n){cin >> a[i] >> b[i];}
#define ALL(a) (a).begin(),(a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) SORT(a);reverse(ALL(a))
#define pb push_back
#define mp make_pair
#define PF first
#define PS second
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
template<typename A, size_t N, typename T>void Fill(A (&array)[N], const T &val){fill( (T*)array, (T*)(array+N), val );}
#define OUT(x) cout << x << endl;
#define OUTD(x) cout << fixed << x << endl;
#define BOUT(b) if(b){OUT("Yes");}else{OUT("No");}
const ll MOD = 1000000007;
const ll INF = 10e9;
#define PI 3.14159265369;
ll dx[4] = {1,-1,0,0};
ll dy[4] = {0,0,1,-1};
ll ddx[8] = {1,1,1,-1,-1,-1,0,0};
ll ddy[8] = {0,1,-1,0,1,-1,1,-1};

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  IN(ll,N);
  vector<P> A(N);
  for(ll i = 0; i<N;i++){
      P PIN = {0,0};
      cin >> PIN.first;
      PIN.second = i;
      A.at(i) = PIN;
  }
  SORT(A);
  ll count = 0;
  for(ll i = 0;i < N; i++){
      if((A.at(i).second % 2) != (i%2)){
          count++;
      }
  }
  OUT(count/2);
}

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

using namespace std;

struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}init;
typedef long long LL;
typedef pair<LL,LL> P;

int main(){
    LL R,C,N;
    cin>>R>>C>>N;
    set<P> memo,b;
    for(int i=0;i<N;i++){
        LL r,c;
        cin>>r>>c;
        b.insert(P(r,c));
        for(int i=-2;i<=0;i++)
            if(1<=r+i&&r+i<=R-2)
                for(int j=-2;j<=0;j++)
                    if(1<=c+j&&c+j<=C-2)
                        memo.insert(P(r+i,c+j));
    }
    vector<LL> cnt(10,0);
    cnt[0]=(R-2)*(C-2)-memo.size();
    for(auto &it:memo){
        int m=0;
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++){
                LL r=it.first+i;
                LL c=it.second+j;
                m+=b.count(P(r,c));
            }
        cnt[m]++;
    }
    for(int i=0;i<10;i++)cout<<cnt[i]<<endl;
}


Measured memory_bytes: 62720
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main()
{
	string str;
	int n;

	cin >> str;
	for (cin >> n; n > 0; n--) {
		string op;
		cin >> op;

		if (op == "print") {
			int a, b;

			cin >> a >> b;
			cout << str.substr(a, b - a + 1) << endl;
		} else if (op == "reverse") {
			int a, b;

			cin >> a >> b;
			reverse(str.begin() + a, str.begin() + b + 1);
		} else if (op == "replace") {
			int a, b;
			string p;

			cin >> a >> b >> p;
			str.replace(a, b - a + 1, p);
		}
	}
}

Measured memory_bytes: 3228
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;using vvi=vector<vi>;using vl=vector<ll>;
using P=pair<int,int>;using PL=pair<ll,ll>;using vp=vector<P>;
const int INF=1<<30,MOD=1000000007;const ll LINF=1ll<<60;
#define _ol3(_1,_2,_3,name,...) name
#define _rep(i,n) _repi(i,0,n)
#define _repi(i,a,b) for(int i=a,i##_l=(b);i<i##_l;++i)
#define REP(...) _ol3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)
#define REPR(i,n) for(int i=n-1;i>=0;--i)
#define REPA(i,v) REP(i,v.size())
#define all(v) (v).begin(),(v).end()
#define bit(n) (1ll<<(n))
#define clamp(n,mi,ma) max(min(n,ma),mi)
#define uniq(v) sort(all(v));v.erase(unique(all(v)),v.end())
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define cho(n,a,b) cout<<((n)?a:b)<<endl
#define YES(n) cho(n,"YES","NO")
#define Yes(n) cho(n,"Yes","No")
#define Poss(n) cho(n,"Possible","Impossible")
template<class T>bool chmax(T&a,const T&b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T&a,const T&b){if(a>b){a=b;return 1;}return 0;}
template<class T>ostream&operator<<(ostream&o,const vector<T>&v){for(auto&&i:v)o<<i<<' ';return o;}
template<class T>istream&operator>>(istream&i,vector<T>&v){for(T&j:v)i>>j;return i;}
template<class T,class U>ostream&operator<<(ostream&o,const pair<T,U>&p){return o<<p.F<<' '<<p.S;}
template<class T,class U>istream&operator>>(istream&i,pair<T,U>&p){return i>>p.F>>p.S;}
template<class T>ostream&operator<<(ostream&o,const set<T>&v){for(auto&&i:v)o<<i<<' ';return o;}
template<class T>ostream&operator<(ostream&o,const T&t){return o<<t;}
template<class T>istream&operator>(istream&i,T&t){return i>>t;}
#ifndef LOCAL
struct ostdmy{
template<class T>ostdmy&operator<<(const T&t){return*this;}
template<class T>ostdmy&operator<(const T&t){return*this;}};ostdmy cer_;
#define cerr cer_
#endif

bool solve(){
    int h,w,n;
    cin>h>w>n;
    P pos;
    cin>pos;
    string s,t;
    cin>s>t;

    int a;

    // up
    a=pos.F;
    REP(i,n){
        if(s[i]=='U')a--;
        if(a<1)return true;
        if(t[i]=='D' && a<h)a++;
    }

    // down
    a=pos.F;
    REP(i,n){
        if(s[i]=='D')a++;
        if(a>h)return true;
        if(t[i]=='U' && a>1)a--;
    }

    // left
    a=pos.S;
    REP(i,n){
        if(s[i]=='L')a--;
        if(a<1)return true;
        if(t[i]=='R' && a<w)a++;
    }

    // right
    a=pos.S;
    REP(i,n){
        if(s[i]=='R')a++;
        if(a>w)return true;
        if(t[i]=='L' && a>1)a--;
    }

    return false;
}

int main(){
    cin.tie(0);ios::sync_with_stdio(0);
    YES(!solve());

    return 0;
}


Measured memory_bytes: 920
import java.util.Scanner;

class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String op = "num";
        int cal = 0;

        while(true) {

            int a = sc.nextInt();
            op = sc.next();
            int b = sc.nextInt();

            if (op .equals("?")) break;
            else if (op .equals("+")) cal = a + b;
            else if (op .equals("-")) cal = a - b;
            else if (op .equals("*")) cal = a * b;
            else if (op .equals("/")) cal = a / b;

            System.out.println(cal);

        }

        sc.close();
    }
}


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

constexpr ll MOD = 2019;

int main() {
  string s;
  ll n;
  cin >> s;
  n = s.size();

  vector<ll> t(n + 1);

  t[n] = 0;
  ll b = 1;
  for (ll i = n - 1; i >= 0; i--) {
    t[i] = (t[i + 1] + b * (s[i] - '0')) % MOD;
    b = (b * 10) % MOD;
  }

  vector<ll> m(MOD, 0);
  for (ll k = 0; k <= n; k++) {
    m[t[k]]++;
  }

  ll sum = 0;
  for (ll i = 0; i < MOD; i++) {
    sum += m[i] * (m[i] - 1) / 2;
  }

  cout << sum << endl;
}


Measured memory_bytes: 5140
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> l[101];
    int matrix[100][100];
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int u,k;
        cin>>u>>k;
        for(int j=0;j<k;j++)
        {
            int tmp;
            cin>>tmp;
            l[u].push_back(tmp);
        }
    }
    
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            matrix[i][j]=0;
        }
    }
    
    for(int i=1;i<n+1;i++)
    {
        for(int j=0;j<l[i].size();j++)
        {
            matrix[i-1][l[i][j]-1]=1;
        }
    }
    
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(j!=0)
                cout<<" ";
            cout<<matrix[i][j];
        }
        cout<<endl;
    }
}

Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int x,y;
	cin>>x>>y;
	char a[105][105];
	bool s[105][105];
	for(int i=1;i<=x;i++)
		for(int j=1;j<=y;j++){
			cin>>a[i][j];
			s[i][j]=1;
		}	
	for(int i=1;i<=x;i++){
		int f=1;
		for(int j=1;j<=y;j++){
			if(a[i][j]=='#'){
				f=0;
				break;
			} 
		}
		if(f){
			for(int j=1;j<=y;j++)
				s[i][j]=false;
		}
	}
	for(int j=1;j<=y;j++){
		int f=1;
		for(int i=1;i<=x;i++){
			if(a[i][j]=='#'){
				f=0;
				break;
			} 
		}
		if(f){
			for(int i=1;i<=x;i++)
				s[i][j]=false;
		}
	}
	for(int i=1;i<=x;i++){
		int f=0;
		for(int j=1;j<=y;j++){
			if(s[i][j]){
				cout<<a[i][j];
				f=1;
			} 
		}
		if(f) cout<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
#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
 
using namespace std;
using namespace __gnu_pbds;
 
#define debug(s) cout << #s << " = " << s << endl
#define all(v) (v).begin(), (v).end()
#define mem(a,val) memset(a, val, sizeof a)
 
#define maxn 100010
#define INF 1e15
#define ff first
#define ss second
#define endl '\n'
typedef long long ll;
 
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

int arr[111];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  int tot = 0;
  for (int i = 1; i <= n; ++i) cin >> arr[i], tot += arr[i];
  int cnt = 0;
  for (int i = 1; i <= n; ++i) {
    if (arr[i] >= ceil((double)tot/(4.*m))) ++cnt;
  }
  if (cnt >= m) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#define NN  0
#define BB -1
static const int MAX = 1005;
static const int INFTY = (1<<21);

int n;

int main(){
  int minv;
  int i, j, k, c, u, v;
  int M[MAX][MAX];
  int d[MAX], col[MAX];

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


  for ( i = 0; i < n; i++ ){
    scanf("%d %d", &u, &k);
    for ( j = 0; j < k; j++ ){
      scanf("%d %d", &v, &c);
      M[u][v] = c;
    }
  }
  


  d[0] = NN;

  for(;;){
    minv = INFTY;
    u = BB;
    for ( i = 0; i < n; i++ ){
      if ( !col[i] && minv > d[i]  ){ 
	u = i;
	minv = d[i];
      }
    }
    if ( u == BB ) break;
    col[u] = 1;
    for ( v = 0; v < n; v++ ){
      if ( !col[v] && M[u][v] != INFTY ){
	if ( d[v] > d[u] + M[u][v] )d[v] = d[u] + M[u][v];
      }
    }
  }

  for ( i = 0; i < n; i++ ) printf("%d %d\n", i, (d[i] ==INFTY?-1:d[i]));

  return 0;
}


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

int main(){
  int n;
  string s;
  cin >> n >> s;
  int m=0,x=0;
  for(int i=0;i<n;i++){
    if(s.at(i)=='I')
      x++;
    else
      x--;
    if(x>m)
      m=x;
  }
  cout << m;
}

Measured memory_bytes: 3616
//
//  code.cpp
//  Cpp
//
//  Created by Yash Jain on 31/03/20.
//  Copyright © 2020 Yash Jain. All rights reserved.
//

#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
list<int>li[200010];
long long subtreesize[200010];
long long dp[200010];
long long ans[200010];
long long fact[200010];
int n;
long long powermod(long long a,long long b){
    if(b == 0)
        return 1;
    else if(b%2 == 0)
        return powermod((a*a)%mod,b/2);
    else
        return (a*powermod((a*a)%mod, b/2))%mod;
}

void dfs1(int v,int par){
    subtreesize[v]=1;
    for(auto e: li[v]){
        if(e!=par){
            dfs1(e,v);
            subtreesize[v]+=subtreesize[e];
        }
    }
}

//dp[i] = (product of  dp[j] if i -> j edge)*(subtreesize[i]-1)!/(product of subtreesize[j]! if i-> j edge)


//rerooting dp[i] * dp[par] * subtreesize[i] / dp[i] * (n-subtreesize[i]-1)!  / (n-subtreesize[i])!
void dfs2(int v,int par){
    long long num = fact[subtreesize[v]-1];
    long long den = 1;
    for(auto e: li[v]){
        if(e!=par){
            dfs2(e,v);
            num = (num * dp[e])%mod;
            den = (den * fact[subtreesize[e]])%mod;
        }
    }
    dp[v] = (num * powermod(den, mod-2))%mod;
    
}

void dfs3(int v,int par){
    if(par != -1){
        ans[v] = 1;
        ans[v] = (ans[v] * dp[par])%mod;
        ans[v] = (ans[v] * subtreesize[v])%mod;
        ans[v] = (ans[v] * powermod(n-subtreesize[v],mod-2))%mod;
    }
    else{
        ans[v] = dp[v];
    }
    dp[v] = ans[v];
    for(auto e: li[v]){
        if(e!=par){
            dfs3(e,v);
        }
    }
    
}

void precompute(){
    fact[0] = 1;
    for(int i=1;i<200010;i++){
        fact[i] = (fact[i-1] * i)%mod;
    }
}

int main(){
    precompute();
    cin>>n;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        li[a].push_back(b);
        li[b].push_back(a);
    }
    dfs1(1,-1);
    dfs2(1,-1);
    dfs3(1,-1);
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<endl;
    }
}


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

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

Measured memory_bytes: 256
n, q = map(int, input().split())
s = input()
quests = []
for _ in range(q):
    quests.append(tuple(map(int, input().split())))

check = []
for i in range(len(s)-1):
    temp = s[i:i+2]
    if temp == "AC":
        check.append(i)

check_begin = [0 for i in range(len(s))]
check_num = 0
for i in range(len(s)):
    if check_num != len(check) and (check[check_num]+1) == i :
        check_num += 1
    check_begin[i] = check_num

#print(check_begin)

check_end = [len(check)-i for i in check_begin]

for quest in quests:
    begin = quest[0]-1
    end = quest[1]-1
    cnt = len(check) - check_begin[begin] - check_end[end]
    print(cnt)




Measured memory_bytes: 25760
using System;

class TestClass {
	static void Main(string[] args) {
		string str = Console.ReadLine();
		string[] array = str.Split(' ');
		float x = float.Parse(array[0]);
		float y = float.Parse(array[1]);
		float a = x * y;
		float b = x * 2 + y * 2;
		Console.WriteLine(a.ToString() + " " + b.ToString());
	}
}


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

using namespace std;

int main() {
    long long n,k;
    vector<long long> x;
    cin >> n >> k;
    for(long long i=0;i<n;i++){
        long long tmp;
        cin >> tmp;
        x.push_back(tmp);
    }
    long long ans = 9999999999999;
    for(long long i=0;i<n-k+1;i++){
        ans = min( ans , abs(x[i+k-1]-x[i]) + min(abs(x[i]),abs(x[i+k-1])));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1400
//
// 桁DP
//
// verified
// [E - Almost Everywhere Zero](https://atcoder.jp/contests/abc154/tasks/abc154_e)
//
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

const ll INF = 1LL << 60;

// i: 何桁目
// j: N 未満か
// k: 0でない数字が表れた回数
ll dp[110][2][100];

string S;
ll K;
int main() {
    cin >> S >> K;
    int N = S.size();

    dp[0][0][0] = 1;

    for (int i = 0; i < N; i++) {
        int D = S[i] - '0';
        for (int j = 0; j < 2; j++) {
            int target = 9;
            if (j == 0) target = D;
            for (int k = 0; k <= K; k++) {
                for (int d = 0; d <= target; d++) {
                    int cnt = 0;
                    if (d != 0) cnt++;
                    dp[i + 1][j || (d < D)][k + cnt] += dp[i][j][k];
                }
            }
        }
    }

    ll ans = 0;
    ans += dp[N][0][K];
    ans += dp[N][1][K];
    cout << ans << endl;
}

Measured memory_bytes: 3684
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
using namespace std;
#define _GLIBCXX_PERMIT_BACKWARD_HASH
#include <ext/hash_map>
using namespace __gnu_cxx;
struct str_hash{size_t operator()(const string& str)const{return __stl_hash_string(str.c_str());}};
typedef long long ll;
typedef unsigned long long ull;
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PDD pair<double,double>
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-8;
const int MAX=1e5+10;
const ll mod=1e9+7;
int main()
{
	int n,m,ans,i;
	string s[111],t;
	while(~scanf("%d",&n))
	{
		ans=0;
		map<string,int> mp;
		for(i=0;i<n;i++)
		{
			cin>>s[i];
			mp[s[i]]++;
		}
		scanf("%d",&m);
		for(i=0;i<m;i++)
		{
			cin>>t;
			mp[t]--;
		}
		for(i=0;i<n;i++)
		{
			ans=max(ans,mp[s[i]]);
		}
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;



signed main()
{
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);  
   
 #ifndef ONLINE_JUDGE
    if(fopen("INPUT.txt","r"))
    {
    freopen ("INPUT.txt" , "r" , stdin);
    freopen ("OUTPUT.txt" , "w" , stdout);
    }
 #endif

// -------------------------------------Code starts here---------------------------------------------------------------------     

   string a;
   cin>>a;
   int n=a.length();
   int cnt=0;
   for(int i=0;i<n;i++)
   {
      if(a[i]=='A')
         cnt++;
   }
   if(cnt>0 && n-cnt>0)
   {
      cout<<"Yes";
   }
   else
   {
      cout<<"No";
   }
   
   

// -------------------------------------Code ends here------------------------------------------------------------------
     clock_t clk;
 	clk = clock();
 
    clk = clock() - clk;
 	cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << "\n";
 	return 0;
 }


Measured memory_bytes: 256
#include<stdio.h>

int A[1000000],c;

int sum(int key)
{
    int a=0,b=c,num;
    while(a<b)
    {
        num=(a+b)/2;
        if(key==A[num]) return 1;
        if(key>A[num])a=num+1;
        else if(key<A[num])b=num;
    }
    return 0;
}
int main()
{
    int i,j,k,tum=0;
    scanf("%d",&c);
    for(i=0;i<c;i++)
    {
        scanf("%d",&A[i]);
        
    }
    scanf("%d",&j);
    for(i=0;i<j;i++)
    {
        scanf("%d",&k);
        if(sum(k))tum++;
        
    }
    printf("%d\n",tum);
    return 0;
}



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

using namespace std;

#define ll long long
#ifdef __APPLE__
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...)
#endif


int main() {
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int n, k;
    scanf("%d %d", &n, &k);
    map<int, int> q;
    for (int i = 0; i < n; ++i) {
        int x;
        scanf("%d", &x);
        ++q[x];
    }
    vector<int> a;
    for (auto it : q) {
        a.push_back(it.second);
    }
    sort(a.begin(), a.end());
    if (a.size() < k) {
        printf("0");
        return 0;
    }
    ll ans = 0;
    for (int i = 0; i < a.size() - k; ++i) {
        ans += a[i];
    }
    printf("%lld", ans);

    return 0;
}  

Measured memory_bytes: 10748
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const long long LINF = 1e18;
int n, m, p;
int edge[5100][3];
vector<int> side[2600][2];
bool path[2600][2];
long long score[2600];
long long ans;

void bfs1(int u) {
  path[u][0] = true;
  queue<int> q;
  q.push(u);
  while(q.size()) {
    for (int v: side[q.front()][0]) {
      if (path[v][0]) continue;
      q.push(v);
      path[v][0] = true;
    }
    q.pop();
  }
}

void bfs2(int v) {
  path[v][1] = true;
  queue<int> q;
  q.push(v);
  while(q.size()) {
    for (int u: side[q.front()][1]) {
      if (path[u][1]) continue;
      q.push(u);
      path[u][1] = true;
    }
    q.pop();
  }
}


int main()
{
  cin >> n >> m >> p;
  
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    edge[i][0] = a;
    edge[i][1] = b;
    edge[i][2] = c - p;
    side[a][0].push_back(b);
    side[b][1].push_back(a);
  }
  
  bfs1(1);
  bfs2(n);
  
  for (int i = 2; i <= n; i++) {
    score[i] = -LINF;
  }
  
  for (int loop = 0; loop < n; loop++) {
    for (int i = 0; i < m; i++) {
      int from = edge[i][0], to = edge[i][1], coins = edge[i][2];
      score[to] = max(score[to], score[from] + coins);
    }
  }
  
  ans = max(0LL, score[n]);
  
  for (int loop = 0; loop < n; loop++) {
    for (int i = 0; i < m; i++) {
      int from = edge[i][0], to = edge[i][1], coins = edge[i][2];
      if (path[to][0] and path[to][1] and score[to] < score[from] + coins) {
        ans = -1;
      }
    }
  }
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 640
#define D(x) cout << #x " = " << x << endl
#define DD(x, y) cout << "(" #x ", " #y ") = (" << x << ", " << y << ")" << endl
#define DDD(x, y, z) cout << "(" #x ", " #y ", " #z ") = (" << x << ", " << y << ", " << z << ")" << endl
#define DV(v) for (auto __macro_vi : v){ cout << __macro_vi << " ";} cout << endl;
#define DA(a, n) for (int __macro_i = 0; __macro_i < n; ++__macro_i) { cout << a[__macro_i] << " "; } cout << endl;
#define REP(i, n) for (int i = 0; i < n; ++i)
#define ALL(v) (v).begin(), (v).end()
#include<iostream>
#include<vector>
#include<cassert>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<tuple>

using namespace std;
using P = pair<char, int>;
int w, h;

vector<string> mp;
vector<vector<P>> memo;
int di[] = {-1, 0, 1, 0};
int dj[] = {0, 1, 0, -1};
P dfs(int i, int j) {

    if (mp[i][j] != '.') return make_pair(mp[i][j], 0);
    if (memo[i][j].second != -1) return memo[i][j];
    memo[i][j].second = 0;

    int cnt = 1;
    char last = '-';
    for (int k = 0; k < 4; ++k) {
        int ni = i + di[k];
        int nj = j + dj[k];
        if (ni < 0 || ni >= h || nj < 0 || nj >= w) continue;
        if (memo[ni][nj].second != -1) continue;
        char c;
        int ncnt;
        tie(c, ncnt) = dfs(ni, nj);
        if (c == '?') last = '?';
        else if (last == '-') last = c;
        else if (last != c && c != '-') last = '?';
        cnt += ncnt;
    }
    memo[i][j] = make_pair(last, cnt);
    //     DD(i, j);
    //     REP(i, h) {
    //     REP(j, w) {
    //         cout << memo[i][j].first;
    //     }
    //     cout << endl;
    // }
    return memo[i][j];
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(1) {
        cin >> w >> h;
        if (w == 0) break;
        mp = vector<string>(h);
        memo = vector<vector<P>>(h, vector<P>(w, make_pair('.', -1)));
        REP(i, h) cin >> mp[i];
        int bcnt = 0;
        int wcnt = 0;
        REP(i, h) REP(j, w) {
            if (memo[i][j].second != -1 || mp[i][j] != '.') continue;
            int cnt;
            char c;
            tie(c, cnt) = dfs(i, j);
            // REP(i, h) {
            //     REP(j, w) {
            //         cout << memo[i][j].first;
            //     }
            //     cout << endl;
            // }
            // DD(c, cnt);
            if (c == 'B') bcnt += cnt;
            if (c == 'W') wcnt += cnt;
        }
        cout << bcnt << " " << wcnt << endl;
    }
}



Measured memory_bytes: 3360
n, m = map(int,input().split())
dangerList = [int(input()) for i in range(m)]
answerList = [0] * (n+2)
answerList[0] = 1
nextDanger = n + 2
if len(dangerList) > 0:
  nextDanger = dangerList.pop(0)
for i in range(n):
  if i == nextDanger:
    if len(dangerList) > 0:
    	nextDanger = dangerList.pop(0)
  else:
    answerList[i+1] = (answerList[i+1] + answerList[i]) % 1000000007
    answerList[i+2] = (answerList[i+2] + answerList[i]) % 1000000007
print(answerList[n])

Measured memory_bytes: 7824
#include <stdio.h>
int main(){
    int n;
    scanf("%d",&n);
    int d[n];
    int i,j;
    long ans=0;
    for(i=0;i<n;i++){
        scanf("%d",&d[i]);
        for(j=i-1;j>=0;j--){
            ans+=d[i]*d[j];
            //printf("%d\n",d[i] * d[j]);
        }
    }

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

Measured memory_bytes: 128
function Main(input) {
    var ex = input[0].split('');
    var result = input[1].split('');

    var sum = 0;
    for (i = 0; i < 3; i++) {
        if (ex[i] === result[i]) {
            sum++;
        }
    }
    console.log(sum);
}

Main(require("fs").readFileSync("/dev/stdin", "utf8").trim().split(/\n|\s/));

Measured memory_bytes: 21064
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a); i > (b); i--)
#define ALL(a) (a).begin(), (a).end()

int main() {
    ll N, V = 0, E = 0;
    cin >> N;
    FOR(i, 1, N + 1) V += i * (N + 1 - i);
    REP(i, N - 1) {
        int u, v;
        cin >> u >> v;
        if (v < u) swap(u, v);
        E += u * (N + 1 - v);
    }
    cout << V - E << endl;
    return 0;
}

Measured memory_bytes: 3640
MOD = 1000000007
N = 100001

fibo = [1, 1] + [0] * N
for i in range(2, N):
    fibo[i] = (fibo[i - 1] + fibo[i - 2]) % MOD

n, m = list(map(int, input().split(" ")))
a_list = [int(input()) for _ in range(m)]
is_ngs = [0] * (n + 2)
for a in a_list:
    is_ngs[a] = 1
for i in range(n):
    if is_ngs[i] and is_ngs[i + 1]:
        print(0)
        exit()
cnts = []
cnt = 0

for i in range(n + 1):
    if is_ngs[i]:
        cnts.append(cnt)
        cnt = 0
        continue
    cnt += 1
cnts.append(cnt)
ans = 1
for c in cnts:
    if c != 0:
        ans *= fibo[c - 1]
# print(is_ngs)
# print(cnts)
print(ans % MOD)


Measured memory_bytes: 11748
#include<bits/stdc++.h>
using namespace std ; 
typedef long long ll;
#define forn(i,e) for(ll i=0; i<e; i++)
#define fors(i,e) for(ll i=s; i<e; i++)
#define endl "\n"
#define zoom ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define PB push_back 
#define MP make_pair
#define F first
#define S second


int main()
{


zoom;

ll x , n ; cin >> x >> n ; 

unordered_map < ll , bool> m ; 

forn(i,n)
{
	ll temp ; cin >> temp ; 
	m[temp] =  1 ;
}

ll l, u ; 
ll flag = 1 ;
ll i = 0; 
while(flag)
{
	if(m.find(x-i) == m.end())
	{
		cout << x - i <<endl ;
		break ;  
	}
	if(m.find(x+i) == m.end())
	{
		cout << x+ i <<endl ;
		break ;  
	}



	i++ ; 
	

}




}

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

typedef long long ll;

int main() {
    int N;
    double total = 0.0;
    double ans = 0.0;
    int a = 1;
    cin >> N;
    vector<int>v(N);
    vector<pair<int, int>>xy(N);

    for (int i = 0; i < N; i++) {
        v[i] = i;
        cin >> xy[i].first >> xy[i].second;
    }

    do {
        for (int i = 1; i < N; i++) {
            int x, y;
            x = pow((xy[v[i]].first - xy[v[i-1]].first), 2);
            y = pow((xy[v[i]].second - xy[v[i-1]].second), 2);
            total += sqrt(x+y);
        }
    } while(next_permutation(v.begin(), v.end()));

    while (N > 0) {
        a *= N;
        N--;
    }
    ans = total/(double)a;

    printf("%.10f\n", ans);
}


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

int main() {
  string S;
  cin>>S;
  int n=S.size();
  long mod=1e9+7;
  vector<vector<long>> dp(n+1,vector<long>(13));
  dp[0][0]=1;
  for(int i=0;i<n;i++){
    for(int j=0;j<13;j++){
      if(S[i]=='?'){
        for(int k=0;k<=9;k++) dp[i+1][(j*10+k)%13]+=dp[i][j],dp[i+1][(j*10+k)%13]%=mod;
      }
      else{
        long k=S[i]-'0';
        dp[i+1][(j*10+k)%13]+=dp[i][j];
        dp[i+1][(j*10+k)%13]%=mod;
      }
    }
  }
  cout<<dp[n][5]<<endl;
}


Measured memory_bytes: 16700
#include <stdio.h>

int main(void)
{
	int i, n, max, rmin, r0, rt;
	scanf("%d",&n);
	scanf("%d",&r0);
	scanf("%d",&rt);
	max = rt - r0;
	if(r0 < rt) {
		rmin = r0;
	} else {
		rmin = rt;
	}
	for(i=2; i<n; i++) {
		scanf("%d",&rt);
		if(rt-rmin > max) {
			max = rt - rmin;
		}
		if(rmin > rt) {
			rmin = rt;
		}
	}
	printf("%d\n",max);
	return 0;
}

Measured memory_bytes: 596
#pragma GCC optimize("Ofast")
/*#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
                      
using namespace std;
                      
template<typename T> void uin(T &a, T b) {
    if (b < a) {
        a = b;
    }
}
                      
template<typename T> void uax(T &a, T b) {
    if (b > a) {
        a = b;
    }
}

#define int long long
#define ghost signed
#define left left228
#define right right228
#define prev prev228
#define list list228

ghost main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int m, k;
	cin >> m >> k;
	if (m == 1 && k == 0) {
		cout << "0 0 1 1\n";
		return 0;
	}
	if (m == 1 && k == 1) {
		cout << -1 << endl;
		return 0;
	}
	if (k < (1 << m)) {
		cout << k << " ";
		for (int i = 0; i < (1 << m); ++i) {
			if (i != k) cout << i << " ";
		}
		cout << k << " ";
		for (int i = (1 << m) - 1; i + 1; --i) {
			if (i != k) cout << i << " ";
		}
		cout << endl;
	} else {
		cout << -1 << endl;
	}
	return 0;
} // kek ;





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

int main(int argc, char const *argv[])
{
	for (int i = 1; i < 10; i++){
		for (int j = 1; j < 10; j++){
			cout<<i<<"x"<<j<<"="<<j*i<<endl;
		}
	}
	return 0;
}


Measured memory_bytes: 3044
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PI 3.141592653589793
#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, a, n) for (int i = a; i < (n); i++)
#define rrep(i, n, k) for (int i = (n); i >= (k); i--);
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vector(size_t a, Ts... ts){return vector<decltype(make_vector<T>(ts...))>(a, make_vector<T>(ts...));}
const int MOD = 1e9+ 7;
const int INF = 2e18;

template< typename T >
struct edge {
    int src, to;
    T cost;

    edge(int to, T cost) : src(-1), to(to), cost(cost) {}

    edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

    edge &operator=(const int &x) {
        to = x;
        return *this;
    }

    operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

template< typename T >
vector< T > dijkstra(WeightedGraph< T > &g, int s) {
    const auto inf = numeric_limits< T >::max();
    vector< T > dist(g.size(), inf);

    using Pi = pair< T, int >;
    priority_queue< Pi, vector< Pi >, greater< > > que;
    dist[s] = 0;
    que.emplace(dist[s], s);
    while(!que.empty()) {
        T cost;
        int idx;
        tie(cost, idx) = que.top();
        que.pop();
        if(dist[idx] < cost) continue;
        for(auto &e : g[idx]) {
            auto next_cost = cost + e.cost;
            if(dist[e.to] <= next_cost) continue;
            dist[e.to] = next_cost;
            que.emplace(dist[e.to], e.to);
        }
    }
    return dist;
}


struct info {
    double x, y, r;
};

signed main() {
    double xs, ys, xt, yt;
    cin >> xs >> ys >> xt >> yt;
    int N;
    cin >> N;
    vector<info> barrier;
    WeightedGraph<double> G(N + 5);
    auto calc = [&](int fromIdx, int toIdx) {
        auto from = barrier[fromIdx], to = barrier[toIdx];
        double xDistance = from.x - to.x, yDistance = from.y - to.y;
        return max(0.0, sqrt(xDistance * xDistance + yDistance * yDistance) - from.r - to.r);
    };
    barrier.push_back({xs, ys, 0});
    for (int i = 1; i <= N + 1; i++) {
        double x, y, r;
        if (i != N + 1) cin >> x >> y >> r;
        else {
            x = xt;
            y = yt;
            r = 0;
        }
        barrier.push_back({x, y, r});
        for (int j = 0; j < i; j++) {
            G[j].emplace_back(i, calc(j, i));
            G[i].emplace_back(j, calc(i, j));
        }
    }
    auto dist = dijkstra<double>(G, 0);
    cout << fixed << setprecision(10) << dist[N + 1] << endl;
}


Measured memory_bytes: 30484
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>

using namespace std;

double pi = M_PI;

int main(void) {
	int r;
	scanf("%d", &r);
	printf("%lf\n", 2 * pi * r);
}

Measured memory_bytes: 3812
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Stream;

public class Main {

    public static void main(String[] args) throws Exception {

        InputStreamReader is = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(is);

        List<String> mylist = new ArrayList<>();

        // 標準入力からの値を変数strinputに代入
        String strinput = reader.readLine();

        while (strinput != null) {

            mylist.add(strinput);
            strinput = reader.readLine();

        }

        String arr01[] = mylist.get(0).split(" ");
        int n = Integer.valueOf(arr01[0]);
        String arr02[] = mylist.get(1).split(" ");

        Stream<String> stream = Arrays.stream(arr02);
        int arr03[] = stream.mapToInt(Integer::parseInt).toArray();
        //昇順ソート
        Arrays.sort(arr03);
        int temp = n / 2;

        System.out.println(arr03[temp] - arr03[temp - 1]);

    }

}


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

int n, m;
long long s;
unsigned long long ans[55];
unsigned long long dp[55][7005];
pair<int, int> refill[200005];
vector<pair<int, pair<long, long> > > g[55];

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

  cin >> n >> m >> s;
  for(int i = 0; i < m; i++) {
    int u, v, a, b;
    cin >> u >> v >> a >> b;
    g[u-1].push_back(make_pair(v-1, make_pair(a, b)));
    g[v-1].push_back(make_pair(u-1, make_pair(a, b)));
  }

  for(int i = 0; i < n; i++) {
    int c, d;
    cin >> c >> d;
    refill[i] = make_pair(c, d);
  }

  for(int i = 0; i < n; i++) for(int j = 0; j < 7005; j++) dp[i][j] = 10e12;

  dp[0][(min(s, 7004ll))] = 0;
  for(int i = 0; i < 700; i++) {
    for(int j = 0; j < n; j++) 
      for(int k = 0; k < 7005-refill[j].first; k++) 
        dp[j][k+refill[j].first] = min(dp[j][k+refill[j].first], dp[j][k]+refill[j].second);

    for(int j = 0; j < n; j++) 
      for(int k = 0; k < 7005; k++) 
        for(auto& a : g[j]) 
          if(k >= a.second.first && dp[j][k] < 10e12) 
            dp[a.first][k-a.second.first] = min(dp[a.first][k-a.second.first], dp[j][k]+a.second.second);
  }

  for(int i = 0; i < n; i++) ans[i] = dp[i][0];
  for(int i = 0; i < n; i++) for(int j = 0; j < 7005; j++) ans[i] = min(ans[i], dp[i][j]);
  for(int i = 1; i < n; i++) cout << ans[i] << endl;
}

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

int main(){
  int A,B,K;
  cin >>A>>B>>K;
  if((A+K-1)<(B-K+1)){
    for(int i=0;i<K;i++){
      cout<<A+i<<endl;
    }
    for(int i=0;i<K;i++){
      cout<<B-K+1+i<<endl;
    }
    return 0;
  }
  for(int i=A;i<B+1;i++){
    cout<<i<<endl;
  }
  return 0;
  return 0;
}

    
    
      

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=5e18;

ll n,m,x[55];
vector<pll> v[55];
ll dp[1<<20];

bool dfs1(ll a,ll b,ll c,ll d) {
  if(a==c) {
    return 1;
  }
  for(auto& i:v[a]) {
    if(i.first!=b&&dfs1(i.first,a,c,d)) {
      x[i.second]^=1<<d;
      return 1;
    }
  }
  return 0;
}

int main() {
  cin >> n;
  for(ll i=1;i<n;i++) {
    ll a,b;
    cin >> a >> b;
    v[a].emplace_back(b,i);
    v[b].emplace_back(a,i);
  }
  cin >> m;
  for(ll i=0;i<m;i++) {
    ll a,b;
    cin >> a >> b;
    dfs1(a,0,b,i);
  }
  dp[0]=1;
  for(ll i=1;i<n;i++) {
    for(ll j=(1<<m)-1;j>=0;j--) {
      dp[j|x[i]]+=dp[j];
    }
  }
  cout << dp[(1<<m)-1] << endl;
}

Measured memory_bytes: 8448
#include<iostream>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<vector>
#include<stdio.h>
using namespace std;

#define long long long
#define ft(i, a, b) for (int i = (long)a ; i <= (long)b ; i++)
#define fd(i, a, b) for (int i = (long)a ; i >= (long)b ; i--)

const int mxN = 1e5 + 5;
const long oo = 1e15;

double pi = 3.14;
double r;

void Solve() {
    printf("%0.2f",2 * r * pi);
}

void FastInput() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
}

void Input() {
    cin >> r;
}

int main() {
    FastInput();
    Input();
    Solve();
}

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

const int mod = 1000000007;
struct mint {
  ll x;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
} comb(1000010);

int main() {
  int n, k; cin >> n >> k;
  vector<mint> ans(k+1);
  for (int i = k; i >= 1; i--) {
    ans[i] = mint(k/i).pow(n);
    for (int j = 2; i * j <= k; j++)
      ans[i] -= ans[i * j];
  }
  mint res = 0;
  for (int i = 1; i <= k; i++)
    res += ans[i] * i;
  cout << res.x << endl;
  return 0;
}

Measured memory_bytes: 19584
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define FOR(i, s, e) for (ll(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (ll(i) = (s); (i) > (e); (i)--)
#define debug(x) cout << #x << ": " << x << endl
#define mp make_pair
#define pb push_back
const ll MOD = 1000000007;
const int INF = 1e9;
const ll LINF = 1e16;
const double PI = acos(-1.0);
int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

/* -----  2017/05/27  Problem: ARC 015 B / Link: http://arc015.contest.atcoder.jp/tasks/arc015_b  ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */

ll N,A,B;

ll ans = 0LL;

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

  cin >> N>>A>>B;
  if (A > B) {
	  cout << 0 << endl;
	  return 0;
  }
  if (N == 1 && A != B) {
	  cout << 0 << endl;
	  return 0;
  }
  ans = B*(N - 1) + A - (A*(N - 1) + B - 1);

  cout << ans << endl;

  return 0;
}


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

using namespace std;

int n;
vector<int> ans[400005];

int main(void)
{
    cin >> n;
    
    int sum = 0, num;
    for(int i = 1; ; i++){
        sum += i;
        if(sum == n){
            num = i;
            break;
        }
        if(sum > n){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    
    if(num == 1){
        cout << 2 << endl;
        cout << 1 << " " << 1 << endl;
        cout << 1 << " " << 1 << endl;
        return 0;
    }
    
    
    
    int id = 4;
    ans[1].push_back(1);
    ans[1].push_back(2);
    ans[2].push_back(1);
    ans[2].push_back(3);
    ans[3].push_back(2);
    ans[3].push_back(3);
    for(int i = 3; i <= num; i++){
        for(int j = 1; j <=i; j++){
            ans[i+1].push_back(id);
            ans[j].push_back(id++);
        }
    }
    
    cout << num+1 << endl;
    for(int i = 1; i <= num+1; i++){
        cout << ans[i].size() << " ";
        for(int j = 0; j < ans[i].size(); j++) cout<< ans[i][j] << " ";
        cout << endl;
    }
    return 0;
}

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

int n, m, q;
long long ans = 0;
vector<int> a(50), b(50), c(50), d(50);

void calc(vector<int> &A) {
  long long cur = 0;
  for (int i = 0; i < q; i++) {
    if (A[a[i]-1] + c[i] == A[b[i]-1]) cur += d[i];
  }
  ans = max(ans, cur);
}

void rec(vector<int> &A, int idx) {
  if (idx < n) {
    for (int nx = A[idx-1]; nx <= m; nx++) {
      vector<int> B(A.begin(), A.end());
      B[idx] = nx;
      rec(B, idx+1);
    }
  } else {
    calc(A);
  }
}

int main() {
  cin>>n>>m>>q;
  for (int i = 0; i < q; i++) cin>>a[i]>>b[i]>>c[i]>>d[i];

  vector<int> A(n, 1);
  rec(A, 1);
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
int main() {
	int n;
	std::cin >> n;
	auto vec = std::vector<int>(n);
	for (auto &v : vec) std::cin >> v;
	std::sort(vec.begin(), vec.end());
	auto map = std::map<int, int>();
	for (const auto &v : vec) {
		if (map.find(v) == map.end()) map.insert(std::make_pair(v, 1));
		else map[v] += 1;
	}
	int sum = 0;
	for (const auto &m : map) {
		sum += (m.first <= m.second) ? m.second - m.first : m.second;
	}
	std::cout << sum << std::endl;
}

Measured memory_bytes: 5120
function main(input) {
    var line = input.split(/\r?\n/g);
    var arr = line[0].split(" ");
    const a = arr[0], b = arr[1];
    console.log(a.repeat(b) < b.repeat(a) ? a.repeat(b) : b.repeat(a));
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 21444
n=int(input())
a=list(map(int,input().split()))
flag=True

if n%2==0:
  if 0 in a or len(set(a))!=n//2:flag=False
else:
  if len([0 for x in a if x==0])!=1 or len(set(a))!=n//2+1:flag=False

print(2**(n//2)%(10**9+7) if flag else "0")

Measured memory_bytes: 14008
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
a.sort(reverse=1)
ans = 0
cnt = 0
i = 1
while cnt < n:
    ans += a[i]
    i += 2
    cnt += 1
print(ans)


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

using namespace std;

// 無限大の値
const long long INF = 1LL << 60;
// DP テーブル
long long dp[100010];

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

int main() {
    // DP テーブル全体を初期化
    for (int i = 0; i < 100010; ++i) dp[i] = INF;

    int N, K;
    cin >> N >> K;
    vector<int> h(N);
    for (int i = 0; i < N; ++i) {
        cin >> h[i];
    }
    dp[0] = 0;
    for (int i = 1; i < N; ++i) {
        for (int k = 1; k <= K; ++k) {
            if (i-k < 0) break;
            chmin(dp[i], dp[i-k]+abs(h[i]-h[i-k]));
        }
    }
    cout << dp[N-1] << endl;
    return 0;
}


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


int main(){
  int N,K;
  cin>>N>>K;
  int ans =1;
  for(int i=0;i<N;i++){
    if(ans*2<ans+K){
      ans = ans*2;
    }else{
      ans += K;
    }
  }
  cout<<ans<<endl;
}

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

int main()
{
    int n;
    cin >> n;
    int a[n];

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

    sort(a, a + n, greater<int>());

    int alice = 0;
    int bob = 0;
    int turn = 1;
    for (size_t i = 0; i < n; i++)
    {
        if (turn == 1)
        {
            alice += a[i];
        }
        else
        {
            bob += a[i];
        }
        turn *= -1;
    }

    cout << alice - bob << endl;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from collections import Counter


def read():
    S = input().strip()
    return S,


def solve(S):
    D = Counter(S)
    if D["N"] != 0 and D["S"] == 0 or D["N"] == 0 and D["S"] != 0:
        return "No"
    if D["E"] != 0 and D["W"] == 0 or D["E"] == 0 and D["W"] != 0:
        return "No"
    return "Yes"


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))


Measured memory_bytes: 9296
#include <stdio.h>

int main(void) {
	int n,g,k[100],temp,sum=0,diff,q,min;
	scanf("%d",&n);
	scanf("%d",&g);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&k[i]);
	}
	for (int i = 0; i < n-1; i++)
	{
		for (int j = 0; j < n-i-1; j++)  
        {
        	if (k[j] > k[j+1]) 
            {
              	temp=k[j];
              	k[j]=k[j+1];
              	k[j+1]=temp;
            }
        }
	}
	for(int i=0;i<n;i++)
	{
		sum+=k[i];
	}
	diff=g-sum;
	min=k[0];
	if(diff==0)
	{
		printf("%d",n);
	}
	else
	{
		q=diff/min;
		printf("%d",n+q);
	}
}


Measured memory_bytes: 128
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())




int n, m;
vector<int> edge[100000];
int s, t;


int dis[100000][3];




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

	cin >> n >> m;
	rep(i,m) {
		int u, v;
		cin >> u >> v;
		u--; v--;
		edge[u].push_back(v);
	}
	cin >> s >> t;
	s--; t--;

	rep(i, n)rep(j, 3)dis[i][j] = -1;
	queue<pair<int, int>> q;
	q.emplace(s, 0);
	dis[s][0] = 0;

	while(!q.empty()) {
		auto p = q.front();
		q.pop();

		for (int v : edge[p.first]) {
			int mod = (p.second + 1) % 3;
			if (dis[v][mod] == -1) {
				dis[v][mod] = dis[p.first][p.second] + 1;
				q.emplace(v, mod);
			}
		}
	}

	cout << (dis[t][0] == -1 ? -1 : dis[t][0] / 3) << endl;



	return 0;
}

Measured memory_bytes: 6912