akhauriyash/Code-Regression huggingface dataset:
//#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <climits>
#include <set>
#include <cassert>

using namespace std;

const int SIZE = 1 << 10;
int pointer = SIZE;
char buffer[SIZE];

char Advance() {
    if (pointer == SIZE) {
        fread(buffer, 1, SIZE, stdin);
        pointer = 0;
    }
    return buffer[pointer++];
}

int Read() {
    int answer = 0, sign = 1;
    char ch = Advance();
    while (!isdigit(ch) && ch != '-')
        ch = Advance();
    if (ch == '-') {
        ch = Advance();
        sign = -1;
    }
    while (isdigit(ch)) {
        answer = answer * 10 + ch - '0';
        ch = Advance();
    }
    return answer * sign;
}

int main() {
    //freopen("tema.in", "r", stdin);
    //freopen("tema.out", "w", stdout);
    int v[5];
    v[0] = 0;
    int n;
    scanf("%d", &n);
    while (n) {
        v[0]++;
        v[v[0]] = n % 10;
        n /= 10;
    }
    if ((v[1] == v[2] && v[2] == v[3]) || (v[2] == v[3] && v[3] == v[4]))
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}


Measured memory_bytes: 128
import math

n, m = map(int, input().split())
ball = list(map(int, input().split()))

lcm = n * m // math.gcd(n, m)

ans = 0
for i in range(lcm // m):
    data = []
    for j in range(m):
        d = ball[(i*m+j) % len(ball)]
        data.append(d)
    ans += (max(data) - min(data))

print(ans)



Measured memory_bytes: 5688
n = input()
nums = input()
nums = nums.split()
nums = list(map(int, nums))
print(' '.join(map(str, nums)))

for idx in range(1, int(n)):
    v = nums[idx]
    j = idx - 1
    while j >= 0 and nums[j] > v:
        nums[j+1] = nums[j]
        j -= 1
    nums[j+1] = v
    print(' '.join(map(str, nums)))




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

bool C(ll X,ll A,ll B){
	for(ll i=max(1LL,X/2-5);i<=min(X+1,X/2+5);i++){
		if(X<A&&i==X+1)break;
		if(i==A)continue;
		ll c=i-(A<=i);
		ll j=X+(B<=X)+1-c;
		if(B<=X&&j<=B)j--;
		if(i*j>=A*B)return 0;
	}
	return 1;
}
int main(){
	int q;cin>>q;
	rep(i,q){
		ll a,b;scanf("%lld%lld",&a,&b);
		if(a>b)swap(a,b);
		ll l=0,r=INT_MAX;
		while(r-l>1){
			ll t=(l+r)/2;
			if(C(t,a,b))l=t;
			else r=t;
		}
		printf("%lld\n",l);
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
map<string,int> tbl;
string input(){ string s;cin>>s;return s;}
int main(){
  int n,m;
  bool open = false;
  cin>>n;
  while(n--){
    tbl[input()]=1;
  }
  cin>>m;
  while(m--){
    string s = input();
    if(!tbl[s]) cout << "Unknown " << s << endl;
    else if(open){
      cout << "Closed by " << s << endl;
      open = false;
    }
    else{
      cout << "Opened by " << s << endl;
      open = true;
    }
  }
  return 0;
}

Measured memory_bytes: 1240
#include <bits/stdc++.h>
#include <unistd.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

#define rep(i,j,n) for(i=j;i<n;i++)
#define repi(i,j,n) for(i=j;i>n;i--)
#define inf 1e18
#define M 1000000007
#define pie 3.141592653589793238
#define ll long long
#define ld long double
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define UQ(x) (x).resize(distance((x).begin(),unique(x.begin(),x.end())))

using namespace std;
using namespace __gnu_pbds; 

template<typename T>
using ordered_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rnd64(chrono::high_resolution_clock::now().time_since_epoch().count());

ll power(ll a,ll m,ll mod){
	ll ans=1;
	while(m){
		if(m%2) ans*=a, ans%=(mod);
		a=(a*a)%(mod);
		m>>=1;
	}
	return ans;
}


void init(ll* a,ll n,ll val){
	for(ll i=0;i<n;i++)
		a[i]=val;
}

vll adj[200001];
ll ans[200001];
ll vis[200001];

ll dfs(ll node) {
	vis[node] = 1;
	ll k = 1;
	for(auto i : adj[node]) {
		if(vis[i]) continue;
		k += dfs(i);
	}
	return k;
}

void dfs2(ll node, ll k) {
	vis[node] = 2;
	ans[node] = k;
	for(auto i : adj[node]) {
		if(vis[i] == 2) continue;
		dfs2(i,k);
	}
}

void solve(){
	ll i,j,_;
	ll n;
	cin >> n;
	vector<pair<pll,ll> >  v(n);
	rep(i,0,n) cin >> v[i].F.F >> v[i].F.S, v[i].S = i;
	sort(v.begin(),v.end());
	list<pll> dq;
	for(auto i : v) {
		if(dq.empty() || dq.front().F > i.F.S) {
			dq.push_front({i.F.S,i.S});
			continue;
		}
		pll k = dq.front();
		dq.pop_front();
		adj[k.S].pb(i.S);
		adj[i.S].pb(k.S);
		while(dq.size() && dq.front().F < i.F.S) {
			adj[i.S].pb(dq.front().S);
			adj[dq.front().S].pb(i.S);
			dq.pop_front();
		}
		dq.push_front(k);
	}
	reverse(v.begin(),v.end());
	dq.clear();
	for(auto i : v) {
		if(dq.empty() || dq.front().F < i.F.S) {
			dq.push_front({i.F.S,i.S});
			continue;
		}
		pll k = dq.front();
		dq.pop_front();
		adj[k.S].pb(i.S);
		adj[i.S].pb(k.S);
		while(dq.size() && dq.front().F > i.F.S) {
			adj[i.S].pb(dq.front().S);
			adj[dq.front().S].pb(i.S);
			dq.pop_front();
		}
		dq.push_front(k);
	}
	rep(i,0,n) {
		if(vis[i] == 0) {
			ll k = dfs(i);
			dfs2(i,k);
		}
	}
	rep(i,0,n) cout << ans[i] << endl;
}

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




Measured memory_bytes: 27228
#include <iostream>
#include <vector>
#include <utility>
#include <map>

using namespace std;
const int LOG = 22;
vector<pair<int,int>> G[100010];
vector<pair<int,pair<int,int>>> H[100010];
int parent[25][100010];
int d[100010],dist[100010];
void dfs(int v, int p){
	for(auto x:G[v]){
		if(x.first==p) continue;
		parent[0][x.first] = v;
		d[x.first] = d[v] + 1;
		dist[x.first] = dist[v] + x.second;
		dfs(x.first,v);
	}
}

void init(int v,int root){
	d[root] = 0; parent[0][root] = -1;
	dfs(root,-1);
	for(int k=0;k+1<LOG;k++){
		for(int i=0;i<v;i++){
			if(parent[k][i]<0){
				parent[k+1][i] = -1;
			}else{
				parent[k+1][i] = parent[k][parent[k][i]];
			}
		}
	}
}

int lca(int u, int v){
	if(d[u]>d[v]) swap(u,v);
	for(int k = 0;k<LOG;k++){
		if((d[v] - d[u]) & (1<<k)){
			v = parent[k][v];
		}
	}
	if(u==v) return u;
	for(int k = LOG-1;k>=0;k--){
		if(parent[k][u]!=parent[k][v]){
			u = parent[k][u];
			v = parent[k][v];
		}
	}
	return parent[0][u];
}

int c[100010] = {},cdist[100010] = {};
vector<int> v[100010];
map<pair<int,int>,pair<int,int>> mp;
void dfs2(int s,int p){
	for(int x:v[s]){
		mp[{s,x}] = {c[x],cdist[x]};
	}
	for(auto x:H[s]){
		if(x.first==p) continue;
		pair<int,int> q = x.second;
		c[q.first]++; cdist[q.first] += q.second;
		dfs2(x.first,s);
		c[q.first]--; cdist[q.first] -= q.second;
	}
}

int solve(int v,int c,int num){
	return dist[v] - mp[{v,c}].second + mp[{v,c}].first*num;
}

int x[100010],y[100010],s[100010],t[100010];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int i,n,q;
	cin >> n >> q;
	for(i=0;i<n-1;i++){
		int a,b,c,d;
		cin >> a >> b >> c >> d;
		a--; b--;
		G[a].push_back({b,d}); G[b].push_back({a,d});
		H[a].push_back({b,{c,d}}); H[b].push_back({a,{c,d}});
	}
	init(n,0);
	for(i=0;i<q;i++){
		cin >> x[i] >> y[i] >> s[i] >> t[i];
		s[i]--; t[i]--;
		v[s[i]].push_back(x[i]); v[t[i]].push_back(x[i]); v[lca(s[i],t[i])].push_back(x[i]);
	}
	dfs2(0,-1);
	for(i=0;i<q;i++){
		cout << solve(s[i],x[i],y[i]) + solve(t[i],x[i],y[i]) - 2*solve(lca(s[i],t[i]),x[i],y[i]) << "\n";
	}
}

Measured memory_bytes: 51504
K=int(input())
li_=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(li_[K-1])


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

int main(){
	int n;
	double t,a;
	cin>>n>>t>>a;
	double temp[n+1];
	for(int i=1;i<=n;i++){
		cin>>temp[i];
		temp[i]=t-temp[i]*0.006;
	}
	double minn=1000000,minv;
	for(int i=1;i<=n;i++){
		if(abs(temp[i]-a)<minn){
			minn=abs(a-temp[i]);
			minv=i;
		} 
	} 
	cout<<minv<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <complex>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
using namespace std;
#define REP(i,n) for(int i = 0; i < (int)n; i++)
#define FOR(i,a,b) for(int i = a; i < (int)b; i++)
#define pb push_back
#define mp make_pair
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef long long ll;
const int INF = 1<<28;
const ll MOD = 1000000007;
const int dx[] = {-1, -1, 0, 1, 1, 0}, dy[] = {0, -1, -1, 0, 1, 1};

int tri[10][10];
int n, c;

bool chk(int i, int j, bool b[10][10]) {
	if(i < 0 || j < 0 || n <= i || n <= j)
		return false;
	else if(tri[i][j] == -1 || b[i][j])
		return false;
	return true;
}

void dfs(int i, int j, int &cnt, bool b[10][10], bool &flg) {
	b[i][j] = true;
	REP(k, 6) {
		int y = i + dy[k], x = j + dx[k];
		if(chk(y, x, b)) {
			if(tri[y][x] == 0)
				flg = true;
			if(tri[i][j] == tri[y][x])
				dfs(y, x, ++cnt, b, flg);
		}
	}
}

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

	while(cin >> n >> c, n|c) {
		vector<pi> v;
		REP(i, 10) REP(j, 10)
			tri[i][j] = -1;
		REP(i, n) REP(j, i+1) {
			cin >> tri[i][j];
			if(tri[i][j] == 0)
				v.pb(mp(i, j));
		}

		int ans = -INF;
		REP(i, v.size()) {
			bool b[10][10] = {};
			tri[v[i].first][v[i].second] = c;
			int sum = 0, zero = 1;
			REP(j, 6) {
				int y = v[i].first + dy[j], x = v[i].second + dx[j];
				if(chk(y, x, b)) {
					if(tri[y][x] == 0 || tri[y][x] == c)
						zero = 0;
					if(tri[y][x]) {
						bool flg = false;
						int cnt = 1;
						dfs(y, x, cnt, b, flg);
						if(flg)
							continue;
						if(tri[y][x] == c)
							sum -= cnt;
						else
							sum += cnt;
					}
				}
			}
			ans = max(ans, sum - zero);
			tri[v[i].first][v[i].second] = 0;
		}
		cout << ans << endl;
	}
	return 0;
}

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

//

#define RESIDUE(u,v) (capacity[u][v] - flow[u][v])
#define RCOST(u,v) (cost[u][v] + h[u] - h[v])
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define LL long long

int dp[10];

int c[10][10];

int nums[10];

int main(){
  int h,w;
  cin>>h>>w;

  REP(i,10){
    REP(j,10){
      cin>>c[i][j];
    }
  }

  REP(i,10)
    nums[i]=0;
  
  int dum;
  REP(i,w){
    REP(j,h){
      cin>>dum;
      if(dum>=0)
	nums[dum]++;
    }
  }

  REP(i,10)
    dp[i]=10000;
  dp[1]=0;
  
  bool bl=true;
  int tmp;
  while(bl){
    bl=false;
    REP(i,10){
      tmp=dp[i];
      REP(j,10){
	dp[i]=min(dp[i],dp[j]+c[i][j]);
      }
      bl=(tmp==dp[i])?bl:true;
    }
  }

  int ret=0;
  REP(i,10)
    ret+=dp[i]*nums[i];
  cout<<ret<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;

inline int read()
{
	int X=0; bool flag=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
	if(flag) return X;
	return ~(X-1);
}

int n,m,w;
int x,y;
map<PII,bool> mp;
vector<int> cnt1,cnt2;
int row[N],col[N];
int maxr,maxc;

int main() {
    //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	n=read();
	m=read();
	w=read();

	for(int i=1;i<=w;++i){
		x=read();
		y=read();

		mp[{x,y}]=true;

		row[x]++;
		col[y]++;

		maxr=max(maxr,row[x]);
		maxc=max(maxc,col[y]);
	}

	for(int i=1;i<=n;++i){
		if(row[i]==maxr) cnt1.pb(i);
	}
	for(int i=1;i<=m;++i){
		if(col[i]==maxc) cnt2.pb(i);
  	}

  	for(int i=0;i<cnt1.size();++i){
  		for(int j=0;j<cnt2.size();++j){
  			if(!mp[{cnt1[i],cnt2[j]}]){
  				printf("%d\n",maxr+maxc);
  				return 0;
  			}
  		}
  	}

  	printf("%d\n",maxr+maxc-1);

    return 0;
}

Measured memory_bytes: 28368
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  ll i, o, t, j, l, s, z;
  cin >> i >> o >> t >> j >> l >> s >> z;
  ll ret1 = (i/2)*2 + o + (j/2)*2 + (l/2)*2;
  ll ret2 = i&&j&&l ? ((i-1)/2)*2 + o + ((j-1)/2)*2 + ((l-1)/2)*2 + 3 : 0;
  cout << max(ret1, ret2) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>

using namespace std;
#define int long long int
const int INF = 1001001001001001LL;
const int MOD = 1000000007;

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

signed main(){
    
    int n, m; cin >> n >> m;
    set<int> s;
    for(int i = 0; i < m; i++){
        int a; cin >> a;
        s.insert(a);
    }
    s.insert(n + 1);

    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    for(int i = 0; i < n; i++){
        if(s.find(i + 1) == s.end()) dp[i + 1] += dp[i];
        dp[i + 1] %= MOD;
        if(s.find(i + 2) == s.end()) dp[i + 2] += dp[i];
        dp[i + 2] %= MOD;
    }
    cout << dp[n] << endl;
    return 0;
}


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

#define rep(a,b) for(int a = 0;a < b;a++)
#define REP(i, x, n) for(int i = x; i < n; i++)
#define P(a) cout << a << endl
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define ssort(v) sort(v.begin(),v.end())
#define rev(v) reverse(v.begin(),v.end())
#define vP(v) for(int i = 0;i < v.size();i++){cout << v[i];if(i != v.size()-1)cout << endl;}
#define vcin(v,n) rep(i,n){int a;cin >> a;v.pb(a);}

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int dx[] = { 1, -1 , 0 , 0 };
int dy[] = { 0,  0,  1, -1 };
ll MOD = 1000000007;

void solve(){
	int n,l;
	cin >> n;
	map<int,int> m;
	rep(i,n){
		int a;
		cin >> a;
		m[a]++;
	}
	cin >> l;
	rep(i,l){
		int a;
		cin >> a;
		if(m[a] > 0){
			m[a]--;
		}else{
			P("NO");
			return;
		}
	}
	P("YES");
}

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


Measured memory_bytes: 9600
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <iomanip>
#define typeof(x) __typeof__(x)
#define int long long int
#define mod(x) ((x % MOD) + MOD) % MOD
#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) (c).begin(),(c).end()
#define RALL(c) (c).rbegin(),(c).rend()
#define SZ(c) (int)((c).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define LB(c,x) (int)(lower_bound(ALL(c),x)-(c).begin())
#define UB(c,x) (int)(upper_bound(ALL(c),x)-(c).begin())
#define COUNT(c,x) UB(c,x)-LB(c,x)
#define UNIQUE(c) SORT(c); (c).erase(unique(ALL(c)),(c).end());
#define COPY(c1,c2) copy(ALL(c1),(c2).begin())
#define PB push_back
#define MP make_pair
#define vec vector

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl;

using namespace std;

typedef pair<int,int> P;
struct edge {
  int to, cost;
};

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

template<typename T> ostream& operator << (ostream& s, const vector<T>& v) {
  int len = v.size();
  s << "[";
  for (int i = 0; i < len; i++) {
    s << v[i]; if (i < len - 1) s << " ";
  }
  s << "]";
  return s;
}


signed main()
{
  int n, m; cin >> n >> m;
  vec<int> x(n), y(m);
  rep(i, 0, n) {
    cin >> x[i];
  }
  rep(j, 0, m) {
    cin >> y[j];
  }

  int xsum = 0, ysum = 0;
  rep(i, 0, n-1) {
    xsum = mod(xsum + (x[i+1]-x[i]) * (i+1) * (n-i-1));
  }
  rep(j, 0, m-1) {
    ysum = mod(ysum + (y[j+1]-y[j]) * (j+1) * (m-j-1));
  }

  cout << mod(xsum * ysum) << endl;

  return 0;
}


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

int n,m,ans = 1e9,cnt[303];
vector<priority_queue<pair<int,int> > > v(303);
bool del[303];

int main(){
    cin >> n >> m;
    for(int i = 0;i < n;++i){
        for(int j = 0, x;j < m;++j){
            scanf("%d",&x);
            v[i].push({m-j,x});
        }
    }
    for(int k = 0;k < m;++k){
        memset(cnt,0,sizeof cnt);
        int mx = 0, nxt;
        for(int i = 0;i < n;++i){
            auto t = v[i].top();
            while(del[t.second]){
                v[i].pop();
                t = v[i].top();
            }
            cnt[t.second]++;
            if(cnt[t.second] > mx){
                mx = cnt[t.second];
                nxt = t.second;
            }
        }
        ans = min(ans,mx);
        del[nxt] = 1;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int n, x;
  cin >> n >> x;
  vector<int> v(n);
  rep(i, 0, n) cin >> v[i];

  ll ans = 0;
  rep(i, 0, n - 1) {
    int w = v[i] + v[i + 1];
    if (w > x) {
      ans += w - x;
      v[i + 1] -= min(v[i + 1], w - x);
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 640
# kが極端に少ないので、下位K個を管理してよさそうな気がする
# -> なんかダメ
# じゃ決め打ちして全探索することにしてみる どうせ長さは最大でKなので
# 時間的に間に合うか微妙な気がする
# -> はい

s = list(input())
k = int(input())
d = {}
for i in range(len(s)):
    for j in range(i, min(i + k, len(s))):
        t = "".join(s[i:j + 1])
        if t not in d:
            d[t] = True
dk = sorted(d.keys())
print(dk[k - 1])


Measured memory_bytes: 74036
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pb push_back
#define sz(x) ((int)x.size())

const int mod = 1000000007;
vector<int> g[100005];
pair<int, int> dfs(int u, int p)
{
    int allwhite = 1, anycolour = 1;
    for(auto &k: g[u])
        if(k != p)
        {
            pair<int, int> t = dfs(k, u);
            allwhite *= t.second;
            allwhite %= mod;
            anycolour *= (t.first+t.second)%mod;
            anycolour %= mod;
        }
    return {allwhite, anycolour};
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 0; i < n-1; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].pb(v); g[v].pb(u);
    }
    pair<int, int> a = dfs(1, 1);
    cout << (a.first+a.second)%mod << endl;
}

Measured memory_bytes: 15908
#include "bits/stdc++.h"
#pragma GCC optimize("O3,Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target ("avx,avx2")

using namespace std;

using ll = long long;
#define all(x) begin(x), end(x)

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	ll sum = 0;
	vector<ll> arr(n);
	for(int i{}; i<n; ++i) cin >> arr[i];
	ll maks = arr[0];
	for(int i{1}; i<n; ++i){
		if(arr[i]<maks){
			sum+=maks-arr[i];
	//		arr[i]+=maks-arr[i];
		}else{
			maks = arr[i];
		}
	}

//deb

//for(auto i : arr)
//	cout << i << " ";

	cout << sum << "\n";








}


Measured memory_bytes: 4776
n,m = [int(x) for x in input().split()]
g = [[] for x in range(n)]
for i in range(m):
    a,b = [int(x)-1 for x in input().split()]
    g[a].append(b)
    g[b].append(a)

d = [-1]*n
d[0] = 0
from collections import deque
q = deque()
q.append(0)
ans = [0]*n
while q:
    p = q.popleft()
    for i in g[p]:
        if d[i]==-1:
            q.append(i)
            d[i] = d[p]+1
            ans[i] = p+1
if min(ans)>=0:
    print("Yes")
    for i in ans[1:]:
        print(i)
else:
    print("No")

Measured memory_bytes: 95360
def main():
    N=int(input())
    H=map(int,input().split())

    m_max=0
    m=0
    crnt=0
    for h in H:
        if h>crnt:
            m=0
        else:
            m+=1
            if m>m_max:
                m_max=m
        crnt=h
    print(m_max)

main()

Measured memory_bytes: 11136
import java.util.*;
 
public class Main {
        public static void main(String[] 麺類総選挙){
            Scanner うどん = new Scanner(System.in);
            String そば = うどん.nextLine();
            int ラーメン = そば.length();
            String 山菜そば[] = そば.split("");
            String[] シチュー = new String[ラーメン];
            String[] 信州そば = new String[ラーメン];
            for(int 稲庭うどん=0;稲庭うどん<ラーメン;稲庭うどん++) {
                シチュー[稲庭うどん] = String.valueOf((稲庭うどん + 1)%2); //白スタート
                信州そば[稲庭うどん] = String.valueOf((稲庭うどん)%2);
            }
            //差分比較
            int 赤いきつね=0;
            int 緑のたぬき=0;
            for(int スパゲッティ=0;スパゲッティ<ラーメン;スパゲッティ++){
                if(!山菜そば[スパゲッティ].equals(シチュー[スパゲッティ])){
                    赤いきつね++;
                }else if(!山菜そば[スパゲッティ].equals(信州そば[スパゲッティ])){
                    緑のたぬき++;
                }
            }
            int 第三回人気投票;
            if (赤いきつね < 緑のたぬき) {
                第三回人気投票 = 赤いきつね;
            }else{
                第三回人気投票 = 緑のたぬき;
            }
            System.out.println(第三回人気投票);
        }
 
}

Measured memory_bytes: 55112
#include <bits/stdc++.h>
using namespace std;
void printDP(vector<vector<int>> DP);
int main() {
  string Nstr;
  cin >> Nstr;
  vector<vector<int>> DP(2, vector<int>(2, 0));
  DP.at(1).at(1) = 1;
  for (int s_i = 0; s_i < Nstr.length(); s_i++) {
    int now_i = s_i % 2;
    int oth_i = (s_i + 1) % 2;
    int t_int = Nstr.at(s_i) - '0';
    DP.at(now_i).at(0) =
        min(DP.at(oth_i).at(0) + t_int, DP.at(oth_i).at(1) + 10 - t_int);
    DP.at(now_i).at(1) =
        min(DP.at(oth_i).at(0) + t_int + 1, DP.at(oth_i).at(1) + 9 - t_int);
    //    printDP(DP);
  }
  int now_i = (Nstr.length() + 1) % 2;
  cout << DP.at(now_i).at(0);
}

void printDP(vector<vector<int>> DP) {
  for (int d_i = 0; d_i < (int)DP.size(); d_i++) {
    int Kplus = DP.at(d_i).size();
    for (int k_i = 0; k_i < Kplus; k_i++) {
      cout << DP.at(d_i).at(k_i) << " ";
    }
    cout << endl;
  }
}


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

int main(){
  int N, a, b;
  long A;
  b = 1000;
  cin >> N;
  for(int i=0; i<N; i++){
    a = 0;
    cin >> A;
    while(A%2==0){
      A = A / 2;
      a++;
    }
    if(a<b){
      b = a;
    }
  }
  cout << b << endl;
}

Measured memory_bytes: 256
import java.io.*;
public class Main{
  public static void main(String[]args){
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    try{
    String line;
    int sum;
    while(true){
      sum = 0;
      line = reader.readLine();
      if(line.equals("0"))
      break;
      String[] x = line.split("");
      int[] y = new int[x.length];
      for(int i=0;i<x.length;i++){
        y[i]=Integer.parseInt(x[i]);
        sum += y[i];
      }
      System.out.printf("%d\n",sum);
}
}catch(IOException e){
  System.out.println(e);
} catch(NumberFormatException e){
  System.out.println("数字が正しくありません");
}
}
}


Measured memory_bytes: 25512
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <bits/stdc++.h>
#include<queue>
#include <numeric>
using namespace std;
 
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
 template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
 
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
 
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define fore(i,a) for(auto &i:a)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
 
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
 
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
 

int main(){
    long long X;
    cin >> X;
    long long num=(long long) pow(10,3);
    long long A=0,B=0;
    bool exsit=false;
    long long ans_A=0,ans_B=0;
    for(long long i=0;i<=num;++i){
        A=(long long)pow(i,5);
        for(long long j=-num;j<=i;++j){
            B=(long long)pow(j,5);
            if(A==X+B) 
            {ans_A=i,ans_B=j,exsit=true;
            break;
            }
        }
        if(exsit==true) break;
    }
    cout << ans_A <<" " << ans_B;
}

Measured memory_bytes: 3952
/*
 * main.c
 *
 *  Created on: 2019/03/30
 *      Author: family
 */


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

int dt[3] = {0};

int main()
{
    scanf("%d %d %d", &dt[0], &dt[1], &dt[2]);
    if( (dt[0]==dt[1]) && (dt[0]==dt[2])) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 128
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
n,k=map(int,input().split())
isExist=True
# 1つの頂点を根とした木の距離が2の頂点対の数
if k > (n-2)*(n-1)//2:
    isExist=False
if isExist:
    side=cmb(n,2)-k
    print(side)
    cnt=0
    for i in range(n):
        for j in range(i+1,n):
            if cnt>=k or j==n-1:
                print(i+1,j+1)
            else:
                cnt+=1
else:
    print(-1)


Measured memory_bytes: 3608
object Main extends App {
  val sc = new java.util.Scanner(Console.in)

  def next() = sc.next
  def nextInt() = Integer.parseInt(next)
  def nextDouble() = java.lang.Double.parseDouble(next)

  def solve(n: Int): Unit = {
    if (n > 0) {
      val xs = List.fill(n)(nextDouble)
      val m = xs.sum / n
      val aa = xs.fold(0.0) { (z, e) => z + (e - m) * (e - m) }
      println(math.sqrt(aa / n))
      solve(nextInt)
    }
  }

  solve(nextInt)
}



Measured memory_bytes: 50012
#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;

template < long long mod >
struct mint {
private:
    long long x;

public:
    mint(long long x = 0) : x((mod + x) % mod) {}
    mint(std::string &s) {
        long long z = 0;
        for (int i = 0; i < s.size(); i++) {
            z *= 10;
            z += s[i] - '0';
            z %= mod;
        }
        this->x = z;
    }
    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) {
        long long n = mod - 2;
        mint< mod > u = 1, b = a;
        while (n > 0) {
            if (n & 1) {
                u *= b;
            }
            b *= b;
            n >>= 1;
        }
        return *this *= u;
    }
    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 operator/(const mint &a) const {
        mint res(*this);
        return res /= a;
    }
    friend std::ostream &operator<<(std::ostream &os, const mint &n) {
        return os << n.x;
    }
    bool operator==(const mint &a) const {
        return this->x == a.x;
    }
};

int main() {
    constexpr int MOD = 998244353;
    int n, s;
    cin >> n >> s;
    vector< int > a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    // dp[i][j] : i番目を右端とする区間
    vector< vector< mint< MOD > > > dp(n + 1, vector< mint< MOD > >(s + 1, 0));
    vector< mint< MOD > > sum(vector< mint< MOD > >(s + 1, 0));
    dp[0][0] = 1;
    sum[0] = 1;
    mint< MOD > ans = 0;
    for (int i = 0; i < n; i++) {
        dp[i + 1][0] = 1;
        for (int j = s; j >= a[i]; j--) {
            dp[i + 1][j] = sum[j - a[i]];
            sum[j] += dp[i + 1][j];
        }
        sum[0] += 1;
        ans += dp[i + 1][s] * (n - i);
    }
    // for (int i = 0; i <= n; i++) {
    //     for (int j = 0; j <= s; j++) {
    //         printf("dp[%d][%d] = ", i, j);
    //         cout << dp[i][j] << endl;
    //     }
    // }
    // dump(sum);
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 70784
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <functional>
using namespace std;

typedef long long ll;

vector<int> e[100003];
int eo[100003];
int p[100003];
pair<int, int> range[100003];
bool visited[100003];

pair<int, int> func(int pos) {
	visited[pos] = true;
	for (int i = 0; i < (int)e[pos].size(); ++i) {
		if (visited[e[pos][i]]) continue;
		pair<int, int> ret = func(e[pos][i]);
		range[pos].first = max(range[pos].first, ret.first - 1);
		range[pos].second = min(range[pos].second, ret.second + 1);
	}
	return range[pos];
}

int main() {
	int n; cin >> n;
	for (int i = 0; i < n - 1; ++i) {
		int a, b; cin >> a >> b;
		--a; --b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	for (int i = 0; i < n; ++i) {
		range[i].first = -1e9;
		range[i].second = 1e9;
		p[i] = -1;
	}

	int k; cin >> k;
	int tp;
	deque<pair<int, int>> st;
	for (int i = 0; i < k; ++i) {
		int v, p_; cin >> v >> p_;
		--v;
		p[v] = p_;
		tp = v;
		range[v].first = p_;
		range[v].second = p_;
	}

	st.push_back({ tp,  p[tp]%2});
	for (int i = 0; i < n; ++i) eo[i] = -1;
	while (!st.empty()) {
		int pos = st.back().first;
		int evod = st.back().second;
		st.pop_back();
		eo[pos] = evod;
		for (int i = 0; i < (int)e[pos].size(); ++i) {
			if (eo[e[pos][i]] != -1) continue;
			st.push_back({ e[pos][i], 1 - evod });
		}
	}
	func(tp);
	for (int i = 0; i < n; ++i) {
		bool flag = false;
		for (int j = range[i].first; j <= range[i].second; ++j) {
			if ((j % 2 + 2)%2 == eo[i]) {
				flag = true;
				break;
			}
		}
		if (!flag) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	vector<int> ans(n, -1);
	deque<pair<int, int>> st2;
	st2.push_back({ tp, p[tp] - 1 });
	while (!st2.empty()) {
		int pos = st2.back().first;
		int v = st2.back().second;
		st2.pop_back();
		if (range[pos].first <= v + 1 && v + 1 <= range[pos].second) {
			ans[pos] = v + 1;
		}
		else if (range[pos].first <= v - 1 && v - 1 <= range[pos].second) {
			ans[pos] = v - 1;
		}

		for (int i = 0; i < (int)e[pos].size(); ++i) {
			if (ans[e[pos][i]] != - 1) continue;
			st2.push_back({ e[pos][i], ans[pos] });
		}
	}
	for (int i = 0; i < n; ++i) cout << ans[i] << endl;
	return 0;
}

Measured memory_bytes: 13184
import java.util.Scanner;

class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int q = sc.nextInt();
		int[] a = new int[q + 1];
		for (int i = 1; i < q + 1; i++)
			a[i] = sc.nextInt();
		sc.close();

		int[] score = new int[n + 1];
		for (int i = 1; i < n + 1; i++)
			score[i] = k;

		for (int i = 1; i < q + 1; i++)
			score[a[i]]++;

		for (int i = 1; i < n + 1; i++)
			System.out.println(score[i] - q > 0 ? "Yes" : "No");

	}
}


Measured memory_bytes: 61916
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;
typedef string::const_iterator State;
#define Ma_PI 3.141592653589793
#define eps 1e-5
#define LONG_INF 1e18
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL
#define MOD 998244353LL
#define seg_size 262144*4
#define REP(a,b) for(long long a = 0;a < b;++a)
vector<int> vertexs[400];
stack<int> gogo;
int visited[400];
void dfs(int now) {
	REP(q, vertexs[now].size()) {
		int going = vertexs[now][q];
		if (visited[going]) continue;
		visited[going] = 1;
		dfs(going);
	}
	gogo.push(now);
}
vector<int> ans[4000];
vector<int> gyaku[4000];
int main() {
	int n, m;
	cin >> n >> m;
	REP(i, m) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		vertexs[a].push_back(b);
		gyaku[b].push_back(a);
	}
	REP(i, n) {
		if (!visited[i]) {
			dfs(i);
			while (gogo.empty() == false) {
				int now = gogo.top(); gogo.pop();
				if (visited[now] == 2) continue;
				visited[now] = 2;
				queue<int> can_visit;
				can_visit.push(now);
				vector<int> nya;
				while (can_visit.empty() == false) {
					int now = can_visit.front(); can_visit.pop();
					nya.push_back(now);
					REP(q, gyaku[now].size()) {
						int go = gyaku[now][q];
						if (visited[go] == 1) {
							visited[go] = 2;
							can_visit.push(go);
						}
					}
				}
				REP(q, nya.size()) {
					REP(j, nya.size()) {
						ans[nya[q]].push_back(nya[j]+1);
					}
				}
			}
		}
	}
	
	REP(i, n) {
		sort(ans[i].begin(), ans[i].end());
		REP(q, ans[i].size()) {
			if (q != 0) cout << " ";
			cout << ans[i][q];
		}
		cout << endl;
	}
}


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

long long mod = 1000000007LL;

int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	long long h, n; cin >> h >> n;
	while(n--){
		long long x; cin >> x;
		h -= x;
	}
	
	if(h <= 0) cout << "Yes";
	else cout << "No";
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int i, j, n, m, x, y, up, down;

  scanf("%d", &n);

  for(i=0; i<n; ++i){
    scanf("%d", &m);

    for(j=0, up=0, down=0; j<m; ++j){
      scanf("%d", &x);

      if(j != 0){
	if(x > y && up < x-y)
	  up = x-y;
	else if(x < y && down < y-x)
	  down = y-x;
      }
      y = x;
    }
    printf("%d %d\n", up, down);
  }

  return 0;
}

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

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL 9223372036854775
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define MOD9 998244353
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

using II = pair<int, int>;

int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }
int extgcd(int a, int b, int &x, int &y) { int g = a; x = 1; y = 0; if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x; return g; }

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

int N, K;
string S;

signed main()
{
  cin >> N >> K;
  cin >> S;
  FOR(n,1,N-1) {
    if(K <= 0) break;
    if(S[n-1] != S[n] && S[n] != S[n+1]) {
      S[n] = S[n-1];
      K--;
    }
  }

  char pre = S[0];
  FOR(n,1,N) {
    if(K <= 0) break;
    if(S[n] == pre) {
      continue;
    } else {
      FOR(k,n,N) {
        if(S[k] != pre) {
          S[k] = pre;
        } else {
          break;
        }
      }      
      K--;
    }
  }

  int ans = 0;
  REP(n,N) {
    if(S[n] == 'L') {
      if(n > 0 && S[n-1] == 'L') ans++;
    } else if(S[n] == 'R') {
      if(n < N-1 && S[n+1] == 'R') ans++;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define REP(x,y,z) for(int x=y;x<=z;x++)
#define MSET(x,y) memset(x,y,sizeof(x))
#define M 200005
#define MOD 1000000007
using namespace std;
using LL = long long;
int n,m,k;
LL fact[M],ans;
LL pw(LL x,LL y) {
    LL res=1, tmp=x;
    while (y) {
        if (y&1) res = (res*tmp)%MOD;
        tmp = (tmp*tmp)%MOD;
        y/=2;
    }
    return res;
}
int main()
{
    fact[0] = 1;
    REP(i,1,M-1) fact[i] = (fact[i-1]*i)%MOD;
    
    while (~scanf("%d %d %d", &n,&m,&k)) {
        ans = 0;
        if (k==1) {
            puts("0");
            continue;
        }

        REP(dis,1,n-1) {
            LL tmp = (LL)m * m % MOD * (n-dis) % MOD;
            tmp = tmp * fact[n*m-2] % MOD * pw(fact[k-2], MOD-2) % MOD * pw(fact[n*m-k], MOD-2) % MOD;
            tmp = tmp * dis % MOD;
            ans = (ans + tmp) % MOD;
        }

        REP(dis,1,m-1) {
            LL tmp = (LL)n * n % MOD * (m-dis) % MOD;
            tmp = tmp * fact[n*m-2] % MOD * pw(fact[k-2], MOD-2) % MOD * pw(fact[n*m-k], MOD-2) % MOD;
            tmp = tmp * dis % MOD;
            ans = (ans + tmp) % MOD;
        }
        printf("%lld\n", ans);
    }
    return 0;
}


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

typedef long long ll;
typedef int64_t i6;
typedef std::vector<std::vector<int64_t> > Graph;

#define rep(i, n) for (int64_t i = 0; i < n; ++i)
#define rep2(i, n) for (int64_t i = 1; i <= n; ++i)
#define repb(i, l, n) for (int64_t i = l; i < n; ++i)
#define repb2(i, l, n) for (int64_t i = l; i <= n; ++i)
#define ALL(v) (v).begin(), (v).end()
#define Sort(x) sort(ALL(x))
#define Sort_rev(x) Sort(x);reverse(ALL(x))
#define Push_back(p, a, b) (p).push_back( make_pair( (a), (b) ) )

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 V,typename T> bool find_num(V v, T num) { if ( find(ALL(v), num) == v.end() ) { return false; } return true; }

int main() {
    int64_t n, k;
    cin >> n >> k;
    int64_t a[n];
    std::vector<int64_t> v;
    int64_t kk = 1;
    rep(i, n) {
        cin >> a[i];
    }
    repb(i, k, n) {
        int64_t ans = 0;
        if ( a[i] > a[i-k] ) ans = 1;
        cout << ( ans ? "Yes" : "No" ) << endl;
    }


        /*
        if ( i < k ) {
            kk *= a[i];
            if ( i == k-1 ) {
                v.push_back(kk);
                // cout << "a " << i << " " << i-k << endl;
                // cout << "a " << v.at(v.size()-1) << endl;
            }
        } else {
            kk = kk/a[i-k]*a[i];
            v.push_back(kk);
            // cout << "a " << i << " " << i-k << endl;
            // cout << "b " << a[i-k] << " " << a[i] << endl;
            // cout << "c " << v.at(v.size()-1) << endl;
        }
    }

    repb(i, 1, v.size()) {
        int64_t ans = 1;
        if ( v[i-1] >= v[i] ) {
            ans = 0;
        }
        cout << ( ans ? "Yes" : "No" ) << endl;
    }*/
    return 0;
}


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

int main(){
  int r, g, b;
  cin >> r >> g >> b;

  if ((100*r + 10* g + b) % 4 == 0){
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
  return 0;
}


Measured memory_bytes: 3636
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define rep1(i, n) for(int (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for(int (i) = (n) - 1; (i) >= 0; (i)--)
#define rrep1(i, n) for(int (i) = (n); (i) >= 1; (i)--)
const ll INF = 1145141919;
const ll MOD = 1000000007;
template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}
template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}

char R[555][555];
char B[555][555];

int main(){


    ll H, W;
    cin >> H >> W;
    rep(y, 555)rep(x, 555){
        R[y][x] = '.';
        B[y][x] = '.';
        if(y % 2)R[y][x] = '#';
        else B[y][x] = '#';
    }
    rep(y, 555){
        R[y][1] = '#';
        B[y][W] = '#';
        R[y][W] = '.';
        B[y][1] = '.';
    }
    rep1(y, H)rep1(x, W){
        char c;
        cin >> c;
        if(c == '.')continue;
        R[y][x] = '#';
        B[y][x] = '#';
    }
    rep1(y, H){
        rep1(x, W)cout << R[y][x];
        cout << endl;
    }
    cout << endl;
    rep1(y, H){
        rep1(x, W)cout << B[y][x];
        cout << endl;
    }

    return 0;
}

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

using namespace std;

typedef pair<int, int> P;

int main() {
  string a, b;
  cin >> a >> b;
  int x = stoi(a + b);
  int sq = sqrt(x) + 0.5;
  if (sq * sq == x) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <ios>
#include <iomanip>
#include <cstdlib>
#include <map>
using namespace std;
int main(void){
  int N;
  cin >> N;
  int x;

  vector<pair<string, int> > pairs(N);
  for(int i=0;i<N;i++){
    cin >> pairs[i].first;
    cin >> x;
    pairs[i].second = 100 - x;
  }

  vector<pair<string, int> > pairs_copy(N);
  for(int i=0;i<N;i++){
    pairs_copy[i].first = pairs[i].first;
    pairs_copy[i].second = pairs[i].second;
  }

  sort(pairs.begin(), pairs.end());
  /*for(int i=0;i<N;i++){
    cout << pairs[i].first << endl;
    cout << pairs[i].second << endl;
  }
  for(int i=0;i<N;i++){
    cout << pairs_copy[i].first << endl;
    cout << pairs_copy[i].second << endl;
  }*/

  vector<int>order(N,0);

  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      if(pairs[i].first == pairs_copy[j].first && pairs[i].second == pairs_copy[j].second){
        order[i] = j + 1;
      }
    }
  }

  for(int i=0;i<N;i++){
    cout << order[i] << endl;
  }

  return 0;
}

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

int main() {
    long long int n,h[100010],dp[100010],i,j,k,mini;
    cin>>n>>k;
    for(i=0;i<n;i++) cin>>h[i];
    dp[0]=0;
    for(i=1;i<n;i++){
        j=max((long long int)0,i-k);
        mini=dp[j]+abs(h[i]-h[j]);
        while(j<i){
            mini=min(mini,dp[j]+abs(h[i]-h[j]));
            j++;
        }
        dp[i]=mini;
    }
    cout<<dp[n-1];
}

Measured memory_bytes: 1792
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <functional>
#include <cmath>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MOD (ll)1000000007

ll power(ll a, ll p)
{
	if (p == 0)
		return 1LL;
	else if (p == 1LL)
		return a;

	ll ret = power(a, p / 2LL);
	ret = (ret * ret) % MOD;
	if (p % 2LL)
		ret = (ret * a) % MOD;
	
	return ret % MOD;
}

ll factorial(ll a)
{
	ll ret = 1;
	for (ll i = 2LL; i <= a; i++)
		ret = (ret * i) % MOD;
	return ret % MOD;
}

int main(void)
{
	ll n, ans = 0, cur;
	scanf("%lld", &n);
	for (ll i = 1; i <= 700LL; i++)
	{
		if (n - i * 3LL < 0)
			continue;

		ll temp = n - i * 3LL;

		ll cur = 1LL;
		for (ll j = temp + i - 1LL; j > temp + i - 1LL - temp; j--)
			cur = (cur * j) % MOD;

		cur = (cur * (power(factorial(temp), MOD - 2LL)) % MOD) % MOD;

		//printf("[%lld]\n", cur);
		ans = (ans + cur) % MOD;
	}
	printf("%lld", ans);
	return 0;
}

Measured memory_bytes: 1732
N = int(input())
A = list(map(int,input().split()))
tmp = 10**9
sum = 0
numFu = 0

for i in range(N):
    if A[i] < 0:
        numFu += 1
    sum += abs(A[i])
    tmp = min(tmp,abs(A[i]))

if numFu % 2 == 0:
    print(sum)
else:
    print(sum - 2*tmp)


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

int main() {
  int n;
  cin>>n;
  string s;
  cin>>s;
  if(n>26)n=n%26;
  for(int i=0;i<s.size();i++){
    if(s[i]+n>90){
      char a=s[i]+n-26;
      cout<<(char)a;
    }else{
      cout<<char(s[i]+n);
    }
  }
  cout<<endl;
  return 0;
}

Measured memory_bytes: 256
import math
d=int(input())
X=list(map(int,input().split()))
Y=list(map(int,input().split()))
p_1=[abs(x-y) for x,y in zip(X,Y)]
print(round(sum(p_1),8))
p_2=[abs(x-y)**2 for x,y in zip(X,Y)]
print(round(math.sqrt(sum(p_2)),8))
p_3=[abs(x-y)**3 for x,y in zip(X,Y)]
print(round(math.pow(sum(p_3),1.0/3.0),8))
p_4=max(p_1)
print(round(p_4,8))


Measured memory_bytes: 5704
import numpy as np
N,M= list(map(int, input().split()))
K = []
S=[]
state_S = np.zeros(N)
for m  in range(M):
    _input = list(map(int, input().split()))
    K.append(_input[0])
    S.append(np.array(_input[1:]))
P = list(map(int, input().split()))
ans=0
for i in range(2 ** N):
    pattern= np.array([i >> bit & 1 for bit in range(N)])
    if all(np.sum(pattern[S[j] -1 ]) % 2 == P[j] for j in range(M)):
        ans += 1
print(ans)











Measured memory_bytes: 14452