fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long 
  4. #define pb push_back
  5. #define mp make_pair
  6. #define mod 1000000007
  7.  
  8. void solve(){
  9.     ll n,m,k;
  10.     cin>>n>>m>>k;
  11.     ll arr[n][m];
  12.     for (ll i = 0; i < n; i++) {
  13.         for(ll j=0;j<m;j++){
  14.             arr[i][j]=-1;
  15.         }
  16.     }
  17.     for (int i = 0; i < k; i++) {
  18.         ll a,b,c;
  19.         cin>>a>>b>>c;
  20.         arr[b-1][c-1]=a;
  21.     }
  22.     ll q;
  23.     cin>>q;
  24.     ll arr_q[q]={0};
  25.     for (ll i = 0; i < q; i++) {
  26.         cin>>arr_q[i];
  27.     }
  28.  
  29.     ll arr1[m+n-1]={0}; //store count in diagonal
  30.     ll arr2[m+n-1]={0}; //store maximum in diagonal
  31.     for (ll i = 0; i < n; i++) {
  32.         for(ll j=0;j<m;j++){
  33.             ll sum=i+j;
  34.             if(arr[i][j]==-1){
  35.  
  36.             }
  37.             else{
  38.                 arr1[sum]++;
  39.                 arr2[sum]=max(arr2[sum],arr[i][j]);
  40.             }
  41.         }
  42.     }
  43.  
  44.     reverse(arr1, arr1 + m+n-1);
  45.     reverse(arr2, arr2 + m+n-1);
  46.     ll arr3[m+n-1]={0};
  47.     ll arr4[m+n-1]={0};
  48.     arr3[0]=arr2[0];
  49.     arr4[0]=arr1[0];
  50.     for (ll i = 1; i < m+n-1; i++) {
  51.         arr3[i]=max(arr3[i-1],arr2[i]);
  52.         arr4[i]=arr4[i-1]+arr1[i];
  53.     }
  54.  
  55.     for (ll i = 0; i < q; i++) {
  56.         if(arr_q[i]>m+n-2){
  57.             cout<<arr3[m+n-2]*arr4[m+n-2]<<endl;
  58.         }
  59.         else{
  60.             cout<<arr3[arr_q[i]]*arr4[arr_q[i]]<<endl;
  61.         }
  62.     }
  63. }
  64.  
  65. int main() {
  66.     ios_base::sync_with_stdio(false);
  67.     cin.tie(NULL);
  68.     cout.tie(NULL);    
  69.     long long int t;
  70.     cin>>t;
  71.     while(t--){
  72.         solve();
  73.     }
  74. 	return 0;
  75. }
  76.  
Runtime error #stdin #stdout 0s 4980KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZwGRAg
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!