akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;
using P = pair<int, int>;

int main(){
    int h, w;
    static string map[2000];
    static P memo[2000][2000];
    
    cin >> h >> w;
    for(int i = 0; i < h; i++) cin >> map[i];
    
    
    for(int i = 0; i < h; i++){
        int s = 0, g = 0;
        while(s < w && map[i][s] == '#'){
            s++;
            g++;
        }
        
        for(; s < w;){
            while(g < w && map[i][g] != '#') g++;
            
            for(int j = s; j < g; j++) memo[i][j].first = (g-s);
            
            s = g;
            while(s < w && map[i][s] == '#'){
                s++;
                g++;
            }
        }
    }
    
    int max = 0;
    
    for(int i = 0; i < w; i++){
        int s = 0, g = 0;
        while(s < h && map[s][i] == '#'){
            s++;
            g++;
        }
        
        for(; s < h;){
            while(g < h && map[g][i] != '#') g++;
                
            for(int j = s; j < g; j++){
                memo[j][i].second = (g-s);
                if(max < memo[j][i].first + memo[j][i].second -1) max = memo[j][i].first + memo[j][i].second -1;
            }
            s = g;
            while(s < h && map[s][i] == '#'){
                s++;
                g++;
            }
        }
    }
    
    cout << max << endl;
    
    return 0;
}

Measured memory_bytes: 35584
#include <iostream>

using namespace std;

int main() {
  int x, y;
  int g2[] = {4, 6, 9, 11};
  cin >> x >> y;
  if (x == 2 || y == 2) {
    cout << "No" << endl;
  } else {
    bool xok = false;
    bool yok = false;
    for (int i = 0; i < 4; i++) {
      if (x == g2[i]) {
        xok = true;
      }
      if (y == g2[i]) {
        yok = true;
      }
    }
    if (xok == yok) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 2996
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,count=0;
  string s,t;
  cin>>n>>s>>t;
  for(int i=1; i<=n; i++){
    if(s.substr(n-i,i)==t.substr(0,i)){//substr(開始地点,取り出す長さ)
      count=i;
    }
  }
  cout<<n*2-count<<'\n';
  return 0;
}




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

using namespace std;

int main(){
  vector<int> x(3);
  for(int i=0;i<3;i++){
    cin >> x.at(i);
  }
  sort(x.begin(),x.end());
  int ans=1;
  for(int i=1;i<3;i++){
    if(x.at(i)!=x.at(i-1))  ans++;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;

int main(){
    int n;cin>>n;
    int l[100000],r[100000];
    rep(i,n){
        cin>>l[i];
        cin>>r[i];
    }
    int ans=0;
    rep(i,n){
        ans += r[i]-l[i]+1;
    }
    cout<<ans<<endl;
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#define F first
#define S second
#define PB push_back
#define MK make_pair
#define REP(i, a, b) for (int i=a; i < b; i++)


bool sort_by(pi c, pi d){
	return c.S < d.S;
}

int main() {
	ll k, a, b, ans=1;
	cin >> k >> a >> b;
	if(b <= a+1) ans = k+1;
	else{
		ans = a;
		k -= (a-1);
		if(k % 2 == 0) ans += (k/2 * (b-a));
		else ans += (k/2 * (b-a)) + 1;
	}
	cout << ans;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
const long long INF = 1LL << 60;
bool mem[100010];
int memo[100010];
int N;
int h[100010];
int DFS(int i) {
  ll ans;
    if(mem[i]==true){
        ans= memo[i];
    }
    else if(i==0){
      	ans=0;
      	mem[0]=true;
    }
  else if(i==1){
    	ans=abs(h[1]-h[0]);
   		 memo[1]=ans;
    	mem[1]=true;
  }
    else{
        ans=min(memo[i-2]+abs(h[i]-h[i-2]),memo[i-1]+abs(h[i]-h[i-1]));
        memo[i]=ans;
		mem[i]=true;
    }
  return ans;
}
int main(void) {
  	cin>>N;
    mem[0]=true;
    rep(i, N) {
        cin >> h[i];
        }
  	vector<int>ans(N);
  		rep(i,N){
          ans[i]=DFS(i);
        }
  		cout<<DFS(N-1)<<endl;
}

Measured memory_bytes: 4456
N = int(input())

A = [0 for _ in range(N+1)]
n = int(N ** 0.5) + 1
for x in range(1, n):
    for y in range(1, n):
        for z in range(1, n):
            v = x*x + y*y + z*z + x*y + y*z + z*x
            if v <= N:
                A[v] += 1
for i in range(1, N+1):
    print(A[i])


Measured memory_bytes: 9488
#include <iostream>

using namespace std;

class LightList
{
private:
	const static int INVALID = -1;
	int front, back;
	int *allocate_array;

public:
	LightList(int size) : 
		front(0), back(0)
	{
		allocate_array = new int[size];
	}
	~LightList()
	{
		delete[] allocate_array;
	}
	void insert(int x)
	{
		allocate_array[front] = x;
		front++;
	}
	void remove(int x)
	{
		for (int i = front - 1; i >= back; i--) {
			if (allocate_array[i] == x) {
				allocate_array[i] = INVALID;
				if (i == front - 1)
					front--;
				if (i == back)
					back++;
				break;
			}
		}
	}
	void deleteFirst()
	{
		front--;
	}
	void deleteLast()
	{
		back++;
	}
	void print()
	{
		int i = front - 1;
		while (i >= back && allocate_array[i] == INVALID) i--;
		cout << allocate_array[i];
		i--;
		for (; i >= back; i--) {
			if (allocate_array[i] != INVALID)
				cout << ' ' << allocate_array[i];
		}
		cout << endl;
	}
};

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

	int n, size = 1000020;
	cin >> n;
	if (n < 1000020) size = n;
	LightList number_list(size);

	for (int i = 0; i < n; i++) {
		char command[12];
		int x;
		cin >> command;
		if (command[0] == 'i') { // insert x
			cin >> x;
			number_list.insert(x);
		}
		else { // delete???
			switch (command[6]) {
			case '\0': // delete x
				cin >> x;
				number_list.remove(x);
				break;
			case 'F': // deleteFirst
				number_list.deleteFirst();
				break;
			case 'L': // deleteLast
				number_list.deleteLast();
				break;
			}
		}
	}
	number_list.print();
	return 0;
}

Measured memory_bytes: 4896
#include<stdio.h>
int N,SS[400010],NN=2147483647;
int hyouka(int a,int b){return a<b?a:b;}
void ssset(int n,int *d){
	int i,t;
	for(N=1;N<n;N*=2);
	for(i=0;i<n;i++)SS[i+N]=d[i];
	for(   ;i<N;i++)SS[i+N]=NN;
	for(i=N-1;i;i--){
		t=hyouka(SS[i*2],SS[i*2+1]);
		SS[i    ]+=t;
		SS[i*2  ]-=t;
		SS[i*2+1]-=t;
	}
}
//[l,r)?????????x??????????????????i??????????????????[a,b)
//ssud(l,r,x,1,0,N);
int ssud(int l,int r,int x,int i,int a,int b){
	int t;
	if(b<=l||r<=a)return SS[i];
	if(l<=a&&b<=r)return SS[i]+=x;
	t=hyouka(ssud(l,r,x,i*2,a,(a+b)/2),ssud(l,r,x,i*2+1,(a+b)/2,b));
	SS[i*2  ]-=t;
	SS[i*2+1]-=t;
	return SS[i]+=t;
}
//[l,r)????????????????????????i??????????????????[a,b)
//ssout(l,r,1,0,N);
int ssout(int l,int r,int i,int a,int b){
	if(r<=a||b<=l)return NN;
	if(l<=a&&b<=r)return SS[i];
	return hyouka(ssout(l,r,i*2,a,(a+b)/2),ssout(l,r,i*2+1,(a+b)/2,b))+SS[i];
}
/*int main(){
	int n,m,d[100010],i,a,b,c,q;
	scanf("%d %d",&n,&m);
	for(i=0;i<n;i++)d[i]=NN;
	ssset(n,d);
	while(m--){
		//for(i=1;i<N*2;i++)printf("%d %d\n",i,SS[i]);printf("\n");fflush(stdout);
		scanf("%d",&q);
		if(q){
			scanf("%d %d",&a,&b);
			printf("%d\n",ssout(a,b+1,1,0,N));
		}
		else{
			scanf("%d %d",&a,&b);
			c=ssout(a,a+1,1,0,N);
			ssud(a,a+1,b-c,1,0,N);
		}
	}
	return 0;
}//*/
int main(){
    int n,m,d[100010],i,a,b,c,q;
    scanf("%d %d",&n,&m);
    for(i=0;i<n;i++)d[i]=0;
    ssset(n,d);
    while(m--){
        //for(i=1;i<N*2;i++)printf("%d %d\n",i,SS[i]);printf("\n");fflush(stdout);
        scanf("%d",&q);
        if(q){
            scanf("%d",&a);
            printf("%d\n",ssout(a-1,a,1,0,N));
        }
        else{
            scanf("%d %d %d",&a,&b,&c);
            ssud(a-1,b,c,1,0,N);
        }
    }
    return 0;
}

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

int main( int argc, char *argv[] )
{
int x;
int y;
int a[ 13 ] = { - 1, 0, 1, 0, 2, 0, 2, 0, 0, 2, 0, 2, 0 };

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

	cin >> x;
	cin >> y;
	if( a[ x ] == a[ y ] )
		cout << "Yes" << endl;
	else
		cout << "No" << endl;

	return 0;
}




Measured memory_bytes: 892
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <complex>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cwchar>
#include <cwctype>
#include <exception>
#include <locale>
#include <numeric>
#include <new>
#include <stdexcept>
#include <limits>
#include <valarray>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <list>
#include <utility>
#include <bitset>
#include <algorithm>
#include <functional>
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int INF=1e9+7;
set<pii> S;
int main(){
	int n,m,u,v;
	scanf("%d%d",&n,&m);
	rep(k,m){
		scanf("%d%d",&u,&v);
		if(u>v)swap(u,v);
		S.insert(MP(u,v));
	}
	for(int k=2;k<n;k++)
	if(S.find(MP(1,k))!=S.end()&&S.find(MP(k,n))!=S.end()){
		printf("POSSIBLE");
		return 0;
	}
	printf("IMPOSSIBLE");
	return 0;
	
}

Measured memory_bytes: 9600
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <iomanip>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<long double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }
#define INF 1LL<<60

struct koji {
    int t, x;
    int flag;

    bool operator<(const koji& other) const {
        if (t < other.t) return true;
        else return false;
    }
};

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<int> S(N), T(N), X(N), D(Q);
    vector<koji> kojis(2*N);
    REP(i, N) {
        cin >> S[i] >> T[i] >> X[i];
        S[i] -= X[i];
        T[i] -= X[i];
        kojis[2*i].t = S[i];
        kojis[2*i+1].t = T[i];
        kojis[2*i].x = X[i];
        kojis[2*i+1].x = X[i];
        kojis[2*i].flag = 1;
        kojis[2*i+1].flag = -1;
    }
    sort(ALL(kojis));
    REP(i, Q) cin >> D[i];

    int k = 0;
    multiset<int> events;
    REP(i, Q) {
        

        while(k < kojis.size() && kojis[k].t <= D[i]) {
            if(kojis[k].flag == 1) events.insert(kojis[k].x);
            else events.erase(events.find(kojis[k].x));
            k++;
        }

        if(events.empty()) {
            cout << -1 << endl;
        } else {
            cout << *events.begin() << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 18432
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

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

	bool can=false;
	for(int i=0;i<=n-1;i++)
	{
		long long mn=i*c-(n-1-i)*d;
		long long mx=i*d-(n-1-i)*c;

		if(a+mn<=b and a+mx>=b)
		{
			can=true;
		}
	}

	cout << (can ? "YES" : "NO" ) << endl;







}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

const long long MOD = 4294967291LL;
const long long INF = 1e18;

int GCD(int a, int b){return b == 0 ? a : GCD(b, a % b);}
long long fast_exp(long long base, long long exp, long long mod = MOD) {
    long long tot = 1;
    for(;exp > 0;exp >>= 1) {
       if((exp & 1) == 1) tot = tot * base % mod;
       base = base * base % mod;
    }
    return tot;
}
long long mult_mod(long long base, long long exp, long long mod = MOD) {
    long long tot = 0;
    for(;exp > 0;exp >>= 1){
       if((exp & 1) == 1) tot = (tot + base) % mod;
       base = base * 2 % mod;
    }
    return tot;
}

struct chash {
    static uint64_t splitmix64(uint64_t x) {x += 0x8e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf54876d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31);}
    size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM);}
    size_t operator()(pair<uint64_t,uint64_t> x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x.first + FIXED_RANDOM)^(splitmix64(x.second + FIXED_RANDOM) >> 1);}
};

// ree always check bounds
// int vs long long
// bitset cheese <3

int main(){

    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n; string s; cin >> n >> s;

    if(n >= 3200)
        cout << s;
    else
        cout << "red";

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#define rep(i, start, end) for (int i = (int)start; i < (int)end; ++i)
#define rrep(i, start, end) for (int i = (int)start - 1; i >= end; --i)
#define iter(i, c) for (auto i = (c).begin(); i != (c).end(); ++i)
#define riter(i, c) for (auto i = (c).rbegin(); i != (c).rend(); ++i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<typename T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return 0;}
template<typename T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return 0;}

struct edge {
    int from, to;
    edge(int f, int t):from(f), to(t) {}
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<edge> E;
    int a, b;
    rep(i, 0, N - 1) {
        cin >> a >> b;
        E.emplace_back(a - 1, b - 1);
    }
    int M;
    cin >> M;
    vector<int> U(M), V(M);
    rep(i, 0, M) {
        cin >> U[i] >> V[i];
        --U[i], --V[i];
    }
    vector<vector<P>> graph(N);
    rep(i, 0, N - 1) {
        graph[E[i].from].emplace_back(E[i].to, i);
        graph[E[i].to].emplace_back(E[i].from, i);
    }
    vector<int> parent(N, -1);
    vector<ll> edge_set(N, 0);  // 根から各頂点までのパスに含まれる辺集合
    queue<int> que;
    que.push(0);
    while (!que.empty()) {
        int node = que.front();
        que.pop();
        rep(i, 0, graph[node].size()) {
            int child_node = graph[node][i].first;
            if (child_node == parent[node]) {
                continue;
            }
            que.push(child_node);
            parent[child_node] = node;
            edge_set[child_node] = edge_set[node] | (1LL << graph[node][i].second);
        }
    }
    ll ans = 0;
    rep(mask, 0, 1 << M) {
        // maskのiビット目が0:i番目の条件を満たす, 1:i番目の条件を満たさない
        ll now_edge_set = 0;
        rep(i, 0, M) {
            if ((mask >> i) & 1) {
                now_edge_set |= (edge_set[U[i]] ^ edge_set[V[i]]);
            }
        }
        int conditional_num = __builtin_popcount(mask);
        if (conditional_num % 2) {
            ans -= 1LL << (N - 1 - __builtin_popcountll(now_edge_set));
        }
        else {
            ans += 1LL << (N - 1 - __builtin_popcountll(now_edge_set));
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main()
{
    int r, g, b;
    scanf("%d %d %d", &r, &g, &b);
    if((100*r+10*g+b)%4==0)
    {
        printf("YES");
    }
    else
    {
        printf("NO");
    }
    return 0;
}


Measured memory_bytes: 256
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#include <bits/stdc++.h>
using namespace std;
int main() {
  long long n;
  cin>>n;
  if(n==2){
    cout<<2<<endl;
    return 0;
  }
  while(true){
    for(int i=2;i<=sqrt(n)+1;i++){
      if(n%i==0){
        break;
      }
      if(i>sqrt(n)){
        cout<<n<<endl;
        return 0;
      }
    }
    n++;
  }
}

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

typedef long long ll;

int atcoder(){
    ll n,m;
    cin >> n >> m;
    ll k = m/n;
    
    while(true){
        if(m%k==0) break;
      	k--;
    }
    cout << k << endl;
    return 0;
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    atcoder();
    return 0;
}


Measured memory_bytes: 256
N = int(input())

dic = [3, 5, 7]

ans = set()
def dfs(s):
    if s:
        if int(s) <= N:
            if len(set(s)) == 3:
                ans.add(s)
        else:
            return
    dfs(s+"3")
    dfs(s+"5")
    dfs(s+"7")

dfs("")
print(len(ans))

Measured memory_bytes: 12628
//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

//vector string deque break continue
#define forn(i, s, f) for (int i = (int)s; i < (int)f; i++)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define fs first
#define sc second
#define pf push_front
#define pb push_back
#define pop_f pop_front
#define pop_b pop_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()

#ifdef DEBUG
#else
    #define cerr if (false) cerr
#endif

template <typename T> istream& operator>>(istream& in, vector <T>& a) {for (auto& i : a) in >> i; return in;}
template <typename T> ostream& operator<<(ostream& out, vector <T>& a)  {for (auto& i : a) out << i << " "; return out;}
template <typename T, typename U> void chkmin(T& a, U b) {if (a > b) a = b;}
template <typename T, typename U> void chkmax(T& a, U b) {if (a < b) a = b;}

#define int long long

main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    vector <int> a(n);
    cin >> a;
    long long bal = 1000, stocks = 0;
    forn (i, 0, n - 1) {
        if (a[i] < a[i + 1]) {
            int t = bal / a[i];
            stocks += t;
            bal -= t * a[i];
        } else {
            bal += a[i] * stocks;
            stocks = 0;
        }
        cerr << bal << " " << stocks << "\n";
    }
    bal += stocks * a[n - 1];
    cout << bal;
    return 0;
}

Measured memory_bytes: 3652
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <stdio.h>
#include <set>
#include <vector>
using namespace std;

int main(){
    string a, b, c;
    cin>>a>>b>>c;
    int am = 0;
    int bm = 0;
    int cm = 0;
    char genzai = 'a';
    char shori;
    while(1){
        if(am==a.size()+1){
            cout<<'A'<<endl;
            break;
        }
        else if(bm == b.size()+1){
            cout<<'B'<<endl;
            break;
        }
        else if(cm == c.size()+1){
            cout<<'C'<<endl;
            break;
        }
        if(genzai=='a'){
            genzai = a[am];
            am++;
            //cout<<"am"<<am<<endl;
        }
        else if(genzai == 'b'){
            genzai = b[bm];
            bm++;
            //cout<<"bm"<<bm<<endl;
        }
        else if(genzai =='c'){
            genzai = c[cm];
            cm++;
            //cout<<"cm"<<cm<<endl;
        }
    }
    return 0;
}


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

int N,M,Q;
ll ans = 0;
int a[60],b[60],c[60],d[60];

void dfs(vector<int> &A) {
    // 数列の長さが N に達したら打ち切り
    if ((int)A.size() == N) {

        // 処理
        ll d_sum=0;
        for (int i = 0; i < Q; i++) {
            if(A[b[i]-1]-A[a[i]-1] == c[i]) {
                d_sum += d[i];
            }
        }
        if(ans < d_sum) ans = d_sum;
        return ;
    }

    int prev_last = (A.empty() ? 1 : A.back());
    for (int v = prev_last; v <= M; ++v) {
        A.push_back(v);
        dfs(A);
        A.pop_back();
    }
}

int main(void) { 
    vector<int> A;
    cin >> N >> M >> Q;
    for(int i=0; i<Q; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    if(Q==1) {
        cout << d[0] << endl;
        return 0;
    }
    dfs(A);
    cout << ans << endl;
}

Measured memory_bytes: 3604
/*{{{*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(LL &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const LL &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1e6+10;
int main(){
    int a,b,c; R(a,b,c);
    if(c<=a+b+1)W(c+b);
    else W(b+a+b+1);
    return 0;
}


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

// Begin {{{
using namespace std;
#define all(x) x.begin(), x.end()
#define rep(i, n) for (i64 i = 0; i < (n); ++i)
#define reps(i, b, e) for (i64 i = (b); i <= (e); ++i)
#define repr(i, b, e) for (i64 i = (b); i >= (e); --i)
#define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__)
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
inline i64 sigma(i64 n) { return n * (1 + n) >> 1; }
inline i64 updiv(i64 n, i64 d) { return (n + d - 1) / d; }
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD = int(1e9) + 7;
#ifndef DEBUG
#define dump(...)
#endif

inline void input() {}
template <class Head, class... Tail>
inline void input(Head&& head, Tail&&... tail) {
  cin >> head;
  input(forward<Tail>(tail)...);
}

inline void outs() { cout << "\n"; }
template <class Head, class... Tail>
inline void outs(Head&& head, Tail&&... tail) {
  cout << head << (sizeof...(tail) ? " " : "");
  outs(forward<Tail>(tail)...);
}

template <class T>
inline void outs(vector<T> &vec) { for (auto &e : vec) cout << e << " \n"[&e == &vec.back()]; }

template <class T>
inline void outs(vector<vector<T>> &df) { for (auto &vec : df) outs(vec); }

inline void outl() { cout << "\n"; }
template <class Head, class... Tail>
inline void outl(Head&& head, Tail&&... tail) {
  cout << head << (sizeof...(tail) ? "\n" : "");
  outl(forward<Tail>(tail)...);
}

template <class T>
inline void outl(vector<T> &vec) { for (auto &e : vec) cout << e << "\n"; }

inline void outn() {}
template <class Head, class... Tail>
inline void outn(Head&& head, Tail&&... tail) {
  cout << head;
  outn(forward<Tail>(tail)...);
}

template <class T>
inline void outn(vector<T> &vec) { for (auto &e : vec) cout << e; }

template <class T>
inline vector<T> make_v(const T &initvalue, size_t sz) {
  return vector<T>(sz, initvalue);
}

template <class T, class... Args>
inline auto make_v(const T &initvalue, size_t sz, Args... args) {
  return vector<decltype(make_v<T>(initvalue, args...))>(sz, make_v<T>(initvalue, args...));
}
// }}} End

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

  var(int, N, K, Q);

  auto point = make_v(K - Q, N);

  rep(i, Q) {
    var(int, a);
    --a;
    point[a] += 1;
  }

  rep(i, N) {
    outl((point[i] > 0) ? "Yes" : "No");
  }

  return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
 
typedef struct pair* ppair;
 
typedef struct pair {
  int first, second;
} pair;
 
 
int size;
pair v[1000000];
int psize;
int preorder[1000000];
 
void swap(ppair a, ppair b) {
  pair t = *a;
  *a = *b;
  *b = t;
}
 
int getp(int begin, int end) {
  int i;
  int p = begin;
  for(i = begin+1; i < end; ++i) {
    if(v[i].first < v[p].first) {
      p = i;
    }
  }
  swap(&v[end-1], &v[p]);
  return end-1;
}
 
void qSort(int begin, int end) {
  int i, j;
  if(begin >= end) return;
  getp(begin,end);
  preorder[psize++] = v[end-1].second;
  if(begin+1 == end) return;
  for(i = begin, j = begin; i < end; ++i) {
    if(v[i].second < v[end-1].second) {
      swap(&v[i], &v[j++]);
    }
  }
  swap(&v[j],&v[end-1]);
  qSort(begin, j);
  qSort(j+1, end);
}
 
int main() {
  int i, j;
  int n, k;
  char s[100];
  size = 0;
  scanf("%d", &n);
  for(i = 0; i < n; ++i) {
    scanf("%s", s);
    if(s[0] == 'i') {
      scanf("%d", &k);
      v[size++] = (pair){i,k};
    } else {
      psize = 0;
      qSort(0, size);
      for(j = 0; j < size; ++j) {
        printf(" %d", v[j].second);
      }
      printf("\n");
      for(j = 0; j < size; ++j) {
        printf(" %d", preorder[j]);
      }
      printf("\n");
    }
  }
  return 0;
}


Measured memory_bytes: 7572
#include <stdio.h>
#include <math.h>

int main()
{
    double x1, x2, x3, y1, y2, y3, xp, yp;
    double s, s1, s2, s3;
    double eps = 1e-10;
    
    while(scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&x1,&y1,&x2,&y2,&x3,&y3,&xp,&yp) != EOF){
        s  = fabs((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)); 
        s1 = fabs((xp - x1) * (y2 - y1) - (yp - y1) * (x2 - x1));
        s2 = fabs((xp - x1) * (y3 - y1) - (yp - y1) * (x3 - x1));
        s3 = fabs((xp - x2) * (y3 - y2) - (yp - y2) * (x3 - x2));
        
        if (fabs(s - (s1 + s2 + s3)) <= eps) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

Measured memory_bytes: 612
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int x2 = in.nextInt();
		int i = 1;
		int x = 1;
		while (i <= 3) {
			x *= x2;
			i++;
		}
		System.out.println(x);

	}

}

Measured memory_bytes: 26188
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <tuple>
#include <stack>

using namespace std;
typedef long long ll;

#define MAX_N 1000000
#define INF 1000000

int a[MAX_N];
int b[MAX_N];


int main() {

  // ---------------------
  // Input
  
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  int N, R;
  cin >> N >> R;

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

  int hoge = 0;
  
  if (N >= 10) cout << R << endl;
  else {
    hoge = R + 100*(10-N);
    cout << hoge << endl;
  }
  
  return 0;
  
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
using P = pair<ll, ll>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i, n) for(ll i=1;i<=(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define INF 1000000000

void solve_abc103_c() {
	ll N;
	ll ans = 0;
	cin >> N;

	vector<ll> a(N);
	rep(i, N) {
		cin >> a[i];
		ans += a[i] - 1;
	}

	cout << ans << "\n";
}

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

	solve_abc103_c();

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
typedef long long lint;
using namespace std;

const int MOD = 1e9+7;
const int MAXN = 112345;
lint fact[MAXN];
lint rfact[MAXN];

lint pow_mod(lint x, lint p) {
    lint ret = 1;
    while (p) {
        if (p%2 == 1) {
            (ret *= x) %= MOD;
        }
        p /= 2;
        (x *= x) %= MOD;
    }
    return ret;
}

lint reverse_mod(lint x) {
    return pow_mod(x, MOD-2);
}

lint calc(int a, int b) {
    lint ret = fact[a+b-1];
    (ret *= rfact[a]) %= MOD;
    (ret *= rfact[b-1]) %= MOD;
    return ret;
}

int main() {
    int N, M;
    cin >> N >> M;
    // 素因数分解
    vector<int> vs;
    int m = M;
    for (int i = 2; i*i <= M; i++) {
        if (m%i==0) {
            int cnt = 0;
            while (m%i == 0) {
                m /= i;
                ++cnt;
            }
            vs.push_back(cnt);
        }
    }
    if (m > 1) {
        vs.push_back(1);
    }
    fact[0] = rfact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = (i * fact[i-1]) % MOD;
        rfact[i] = reverse_mod(fact[i]);
    }
    lint ans = 1;
    for (const int el : vs) {
        (ans *= calc(el, N)) %= MOD;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2048
#include<bits/stdc++.h>
const long long INF = LLONG_MAX / 2;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i,r,n) for(int i = (ll)(r); i < (ll)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ll long long int
#define ALL(x) (x).begin(),(x).end()
using namespace std;
ll ans = 0, sum = 0, n, k, counter = 0, w, h;
string s;
vector<ll> v;
vector < pair<ll, ll > > vp;
vector<vector<ll> > vv(50, vector<ll>(50, INF));
vector<string> vs;

int main() {
	cin >> s;
	char a[100];
	REP(i, 100) {
		cin >> a[i];
	}
	cout << 'A' << a[0] << 'C' << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define INF 1<<29
using namespace std;
main(){
  int m,n;
  while(cin>>m>>n,n){
    int a1[n][n],a2[n][n],q,w,e,r;
    r(i,n)r(j,n){
      if(i==j)a2[i][j]=a1[i][j]=0;
      else a2[i][j]=a1[i][j]=INF;
    }
    while(m--){
      scanf("%d%d%d%d",&q,&w,&e,&r);q--;w--;
      a1[q][w]=a1[w][q]=e;
      a2[q][w]=a2[w][q]=r;
    }
    r(k,n)
    #pragma omp parallel
    r(i,n)
    #pragma omp parallel
    r(j,n){
      a1[i][j]=min(a1[i][j],a1[i][k]+a1[k][j]);
      a2[i][j]=min(a2[i][j],a2[i][k]+a2[k][j]);
    }
    cin>>e;
    while(e--){
      scanf("%d%d%d",&q,&w,&r);q--;w--;
      if(r)cout<<a2[q][w]<<endl;
      else cout<<a1[q][w]<<endl;
    }
  }
}

Measured memory_bytes: 3288
#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(0);
using namespace std;
using ii = pair<int, int>;
using ll = long long int;




int main (){
	FASTIO;
	int n; cin >> n;
	n %= 1000;
	
	cout << ((1000 - n == 1000) ? 0 : 1000 - n);

	return 0;
}


Measured memory_bytes: 3660
#include<iostream>

using namespace std;

int main()
{
	long long N;
	long long *A;

	cin >> N;
	A = new long long[N];

	long long ans = 0;

	for(int i=0;i<N;i++)
	{
		cin >> A[i];
	}

	long long sum = 0;

	for(int i=N-2;i>=0;i--)
	{
		long long sub = A[i] * ((sum + A[i+1])%1000000007);
		ans += sub%1000000007;
		sum += A[i+1];
	}

	cout << ans%1000000007 << endl;

	return 0;
}

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

typedef unsigned long long int ull;
typedef long double ldb;
typedef long long int ll;

#define MOD1        1000000007
#define MOD2        998244353
#define PI          3.1415926535897932384626433832795
#define FILL(a, value) memset(a, value, sizeof(a))
#define BOOST       ios_base::sync_with_stdio(false); cin.tie(NULL)
#define what_is(x)  cerr << #x << " is " << x << endl;
#define ASSERT(left,operator,right) { if(!((left) operator (right))){ std::cerr << "ASSERT FAILED: " << #left << #operator << #right << " @ " << __FILE__ << " (" << __LINE__ << "). " << #left << "=" << (left) << "; " << #right << "=" << (right) << std::endl; } }

#define rep01(k,n)      for (ll i=k; i<n; i++)
#define rep02(k,n)      for (ll j=k; j<n; j++)
#define rep03(k,n)      for (ll k=k; k<n; k++)
#define rep11(k,n)      for (ll i=k; i<=n; i++)
#define rep12(k,n)      for (ll j=k; j<=n; j++)
#define rep13(k,n)      for (ll k=k; k<=n; k++)
#define repIT(c,it)     for(typeof(c.begin()) it = c.begin(); it != c.end(); ++it)
#define all(c)      c.begin(), c.end()

using namespace std;

const double pi = acos(-1.0);
const double epsilon = 1e-9;        // Add epsilon when casting double to int to avoid rounding pitfall issues, eg, 0.94*8178 in int
const int maxn = 1e6+10;


void solve()
{
    ll n;
    cin >> n;
    multiset<ll, greater<ll> > a;

    for(int i = 0; i < n; i++)
    {
        ll el;
        cin >> el;
        a.insert(el);
    }

    ll al = 0 , bob = 0;

    int i = 0;
    while(a.size())
    {
        if(i % 2)
            al += *a.begin();
        else
            bob += *a.begin();

        i++;
        a.erase(a.begin());
    }

    //cout << al << " " << bob << "\n";
    cout << abs(al-bob);
    
}

int main()
{
    

    int t = 1;
    //cin >> t;
    while(t--)
        solve();

    cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;
    return 0;
}

Measured memory_bytes: 3728
/*input
2
10 10
*/
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define f first
#define s second
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
int const mod = 1e9+7;
int power(int x, int y, int mod = 2e18){ int ans = 1;x %= mod;while(y){if(y&1)ans = (x * ans) % mod;x = (x * x) % mod;y >>= 1;}return ans;}
int gcd(int a , int b){if(a==0)return b;return gcd(b%a,a);}
int n;
int a[100001];
int dp[100001];
int solve(int i)
{

	if(i>=n)
	{
		return 0;
	}
	if(dp[i]!=-1)
		return dp[i];
	dp[i]=min(abs(a[i]-a[i+1])+solve(i+1),abs(a[i]-a[i+2])+solve(i+2));
	return dp[i];
}

signed main() {
	IOS;
	memset(dp,-1,sizeof(dp));
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	a[n]=a[n-1];
	cout<<solve(0);
	
return 0;
}

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

int main(void) {
	int N;
	cin >> N;
	int A[N + 1];
	int boss;
	for (int i = 1; i <= N; i++)
		A[i] = 0;
	for (int i = 1; i < N; i++) {
		cin >> boss;
		A[boss]++;
	}
	for (int i = 1; i <= N; i++)
		cout << A[i] << endl;
	return 0;
}

Measured memory_bytes: 4388
#!/usr/bin/env python3
import sys


def solve(A: int, B: str):
    b=int(B[0])*100+int(B[2:])
    print(b*A//100)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = str(next(tokens))  # type: str
    solve(A, B)

if __name__ == '__main__':
    main()


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

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

  int sumDigits = 0;
  int a, b, c, d; // a:nと値の等しいもの。b:n以下の最大の10の累乗。c:nと値が等しいもの。

  a = n;
  b = 1;

  for (int i=0;a>9;i++) {
    a /= 10;
    b *= 10;
  };

  c = n;
  for (int i=0;b >= 1;i++) {
    int e = c / b;
    sumDigits += e;

    c %= b;
    b /= 10;
  }

  if (n % sumDigits == 0) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MAX 100005
struct Node{int p,l,r;};
Node T[MAX];
int n,D[MAX],H[MAX];
void depth(int u,int d){
  if(u==-1)return;
  D[u]=d;
  depth(T[u].l,d+1);
  depth(T[u].r,d+1);
}
int hei(int u){
  int h1=0,h2=0;
  if(T[u].l!=-1)h1=hei(T[u].l)+1;
  if(T[u].r!=-1)h2=hei(T[u].r)+1;
  return H[u]=max(h1,h2);
  
}

int sibl(int u){
  if(T[u].p==-1)return -1;
  if(T[T[u].p].l!=u&&T[T[u].p].l!=-1)return T[T[u].p].l;
  if(T[T[u].p].r!=u&&T[T[u].p].r!=-1)return T[T[u].p].r;
  return -1;
}
void print(int u){ 
  cout << "node " << u << ": ";
  cout << "parent = " << T[u].p << ", ";
  cout << "sibling = " << sibl(u) <<", ";
  int deg=0;
  if(T[u].l!=-1)deg++;
  if(T[u].r!=-1)deg++;
  cout << "degree = "<<deg <<", ";
  cout << "depth = " << D[u] << ", ";
  cout << "height = " << H[u] << ", ";
  if(T[u].p==-1)cout << "root";
  else if(T[u].l==-1&&T[u].r==-1)cout << "leaf";
  else cout << "internal node";
  cout << endl;
}
int main(){
  int v,l,r,root = 0;
  cin >> n;
  for(int i=0;i<n;i++)T[i].p=-1;
  for(int i=0;i<n;i++){
    cin >> v >> l >> r;
    T[v].l=l;
    T[v].r=r;
    if(l!=-1)T[l].p=v;
    if(r!=-1)T[r].p=v;
  }
  for(int i=0;i<n;i++)if(T[i].p==-1)root=i;
  depth(root,0);
  hei(root);
  for(int i=0;i<n;i++)print(i);
  return 0;
}

 

Measured memory_bytes: 3108
//2017-10-15
//miaomiao
//
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;

#define LL long long
#define Set(a, v) memset(a, v, sizeof(a))
#define For(i, a, b) for(int i = (a); i <= (int)(b); ++i)

#define N (1000+5)

const int P = 1e9 + 7;

int Pow(LL a, LL anum){
	a %= P;
	int ret = 1;

	while(anum){
		if(anum & 1) ret = 1ll * ret * a % P;
		a = 1ll * a * a % P; anum >>= 1;
	}

	return ret;
}

char mp[N][N];

struct Matrix{
	int h[2][2];

	Matrix(int op = 0){
		Set(h, 0);
		if(op) h[0][0] = h[1][1] = 1;
	}

	Matrix operator *(const Matrix &rhs)const{
		Matrix ret;
		For(i, 0, 1) For(j, 0, 1) For(k, 0, 1)
			(ret.h[i][k] += 1ll * h[i][j] * rhs.h[j][k] % P) %= P;
		return ret;
	}

	Matrix operator ^(LL knum){
		Matrix ret(1), a = *this;
		while(knum){
			if(knum & 1) ret = ret * a;
			a = a * a; knum >>= 1;
		}

	//	printf("%d %d\n%d %d\n", ret.h[0][0], ret.h[0][1], ret.h[1][0], ret.h[1][1]);
		return ret;
	}
}a, tmp;

int main(){
	int n, m;
	LL rk;

	scanf("%d%d%lld", &n, &m, &rk);
	For(i, 1, n) scanf("%s", mp[i]+1);

	int ncnt = 0, mcnt = 0, cnt = 0;

	For(i, 1, n) For(j, 1, m) cnt += mp[i][j] == '#';
	For(i, 1, n) ncnt += (mp[i][1]=='#' && mp[i][m]=='#');
	For(i, 1, m) mcnt += (mp[1][i]=='#' && mp[n][i]=='#');
	
	if(ncnt && mcnt) puts("1");
	else if(!ncnt && !mcnt) printf("%d\n", Pow(cnt, rk-1));
	else{
		int rnum = 0;
		if(ncnt){
			For(i, 1, n) For(j, 1, m-1)
				if(mp[i][j]=='#' && mp[i][j+1]=='#') --rnum;
		}else{
			For(i, 1, m) For(j, 1, n-1)
				if(mp[j][i]=='#' && mp[j+1][i]=='#') --rnum;
		}

	//	printf("cnt = %d rnum = %d ncnt = %d mcnt = %d\n", cnt, rnum, ncnt, mcnt);
		a.h[0][0] = cnt; a.h[0][1] = rnum; a.h[1][1] = max(ncnt, mcnt);
		tmp.h[0][0] = tmp.h[1][0] = 1;

		printf("%d\n", (((a^(rk-1)) * tmp).h[0][0]+P) % P);
	}

	return 0;
}

Measured memory_bytes: 1280
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;
typedef int itn;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef map<int, int> M;
typedef pair<int, int> P;

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

    int n, y;
    cin >> n >> y;

    for (int i = 0; i <= n; ++i)
    {
        for (int j = 0; j <= (n-i); ++j)
        {
            int k = n - i - j;
            if ((10000 * i + 5000 * j + 1000 * k) == y)
            {
                cout << i << " " << j << " " << k << endl;
                return 0;
            }
        }
    }
    cout << "-1 -1 -1"  << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>

int main(){
    std::string four;
    std::cin >> four;
    int count;
    int count2;
    count2 = 0;
    for (size_t i = 0; i < 3; i++)
    {
        /* code */
        count = 0;
        for (size_t j = 0; j < 4; j++)
        {
            /* code */
            if (four[i] == four[j])
            {
                /* code */
                count += 1;
            }
            
        }
        if (count == 2)
        {
            count2 += 1;
        }
    }
    if (count2 == 3)
        {
            std::cout << "Yes" << std::endl;
        }
    else
        {
            /* code */
            std::cout << "No" << std::endl;
        }
    //std::cout << count << ", " << count2 << std::endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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; }



int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(25);

  int a, b;
  cin >> a >> b;

  cout << (a + b == 15 ? '+' : (a * b == 15 ? '*' : 'x')) << '\n';


  

  
  return 0;
}

Measured memory_bytes: 256
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define PR pair
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define REP(i, x, y)   for(int i = (int)(x); i <= (int)(y); i++)
#define FOR(i, x, y)   for(int i = (int)(x); i <  (int)(y); i++)
#define PER(i ,x, y)  for(int i = (int)(x); i >= (int)(y); i--)
#define CH	         ch = getchar()
#define Exit(...)    printf(__VA_ARGS__), exit(0)
#define dln()        fprintf(stderr,"\n")
#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef double	  db;
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI > VII;
typedef PR<int,int> PII;
typedef vector<PII> VPI;
const	int inf=2e9;
const	LL Inf=1e10;
const	int P=1e9+7;
const	int N=1005;

inline LL IN(){
	LL x = 0;
	int ch = 0, f = 0;
	for (CH; ch != -1 && (ch < 48 || ch > 57); CH) f = (ch == '-');
	for (; ch >= 48 && ch <= 57; CH) x = (x << 1) + (x << 3) + ch - '0';
	return f ? (-x) : x;
}
template<typename T> inline int chkmin(T &a, const T &b){if(b < a) return a = b, 1; return 0;}
template<typename T> inline int chkmax(T &a, const T &b){if(b > a) return a = b, 1; return 0;}

void renew(int &x, const int &y){
	x += y;
	if(x >= P) x -= P;
	if(x <  0) x += P;
}

int Pow(int x, int y, int p){
	int a = 1;
	for (; y; y >>= 1, x = (LL)x * x %p) if(y & 1) a=(LL)a * x%p;
	return a;
}

int n, m;
int dp[305][305][305];
int main(){
	scanf("%d%d", &n, &m);
	dp[0][1][1] = 1;
	REP(i, 0, m)
	REP(j, 0, n)
	REP(k, 0, j){
		int val = dp[i][j][k];
		if(!val) continue;
		renew(dp[i + 1][j + 1][k], (LL)val * (n - j) % P);
		renew(dp[i + 1][j][k], (LL)val * (j - k) % P);
		renew(dp[i + 1][j][j], (LL)val * k % P);
	}
	printf("%d\n", dp[m][n][n]);
	return 0;
}

Measured memory_bytes: 55552
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define PI 4*atan(1.0)
typedef long long ll;
typedef long double ld;
using namespace std;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
const int SIZE=205;
//int arr[SIZE]={};
//ここまでテンプレ
int main(){
	char s[3];
	cin>>s;
	for(int i=0;i<strlen(s);i++){
		if(s[i]=='9'){
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
#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);

  ll n;
  cin >> n;

  string ans = "";
  while (n) {
    ll rem = n % 26;
    if (rem == 0) {
      ans += 'z';
      n--;
    } else
      ans += (char)('a' + rem - 1);
    n /= 26;
  }

  reverse(ans.begin(), ans.end());
  cout << ans << endl;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)(b); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int n;
    cin >> n;
    ll a[n];
    rep(i, 0, n) {
        cin >> a[i];
    }
    ll sum = 0;
    rep(i, 0, n) sum ^= a[i];
    rep(i, 0, n) {
        ll ans = sum ^ a[i];
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 5128
from collections import deque
H,W = map(int,input().split())
L = []
for i in range(H):
  L.append(list(input()))
TF = []
for i in range(H):
  K = [False]*W
  TF.append(K)
dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]
que = deque([[0,0]])
TF[0][0] = True
ans = 0
cntblack,cntwhite = 0,0
[cury,curx] = [0,0]
if L[0][0] == '#':
  cntblack += 1
else:
  cntwhite += 1
while [cury,curx] != [H-1,W-1]:
  if len(que) != 0:
    cur = que.popleft()
    TF[cur[0]][cur[1]] = True
    for i in range(4):
      if 0 <= cur[0]+dy_dx[i][0] <= H-1 and 0 <= cur[1]+dy_dx[i][1] <= W-1:
        if L[cur[0]+dy_dx[i][0]][cur[1]+dy_dx[i][1]] != L[cur[0]][cur[1]]:
          if TF[cur[0]+dy_dx[i][0]][cur[1]+dy_dx[i][1]] == False:
            TF[cur[0]+dy_dx[i][0]][cur[1]+dy_dx[i][1]] = True
            if L[cur[0]+dy_dx[i][0]][cur[1]+dy_dx[i][1]] == '#':
              cntblack += 1
            else:
              cntwhite += 1
            que.append([cur[0]+dy_dx[i][0],cur[1]+dy_dx[i][1]])
  else:
    ans += cntblack*cntwhite
    cntblack,cntwhite = 0,0
    if TF[cury][curx] == False:
      que.append([cury,curx])
      if L[cury][curx] == '#':
        cntblack += 1
      else:
        cntwhite += 1
    else:
      if curx != W-1:
        curx +=1
      elif cury != H-1:
        cury += 1
        curx = 0
      else:
        print(ans)
        exit()
print(ans)

Measured memory_bytes: 57308